What sorting algorithm should be used for the scenario below?

Question

The above task "You are working on an embedded device (ATM), which has only 4 KB of free memory, and you want to sort 2,000,000 transactions with canceling the history by the amount withdrawn (discarding the original transaction order)."

For this problem statement, for me, we should use merge sort, is there a problem with this sort algorithm?

Answer 1

This is a problem with embedded systems. They have limited memory for work.

My answer is 2 parts.

1. The best view in the algorithmic perspective

Hands down do not make sense, at least to talk about using types of bubbles, inserts, choices, because they are not very effective in a reasonable size and performance.

Below are some advanced sortings with the worst temporal and spatial complexity.

Quick Sort, O (nn) ---- O (nlog (n))

Combine sorting, O (n * log (n)) ---- O (n)

Tim sort, O (n * log (n)) ---- O (n)

Heap Sort, O (n * log (n)) ---- O (1)

shell sort, O (n * log (n) ^ 2) ---- O (1)

Bucket Sort, O (n * n) ---- O (n)

Radix sort, O (nk) ---- O (n + k)

So, since you need to save memory and speed up processing time, I think heap sorting will be the best alternative here, since in worst cases it also works under O (n * log (n)) and O (1) time and space complexity .

2. Performance

Since high performance is critical to this scenario, you are considering code optimization using EEPROM and expanding memory .

Answer 2

You are definitely looking for an algorithm that is much smaller than O(n) , since 2 million transactions are likely to take much more than 4 KB ...

the complexity of the space gives the amount of memory needed to sort by input size in the worst case. With such low free memory, you cannot afford to use an algorithm that takes up a lot of space.

Combining sorting is an O(n) space, so you'd better look for something else.

Something like O(log n) would be great, since the natural logarithm of 2 million, for example, is ~ 15.

See this table , which displays

• Quick sort
• Bubble Sort
• Heap Sort
• Insert Sort
• and shell sorting

as the maximum free O(log n) .

Answer 3

If you want to use any recursive algorithm, you should consider the amount of memory you need (a stack) for the parameters and return the addresses to the stack for each call to the recursion method. 2,000,000 means that every algorithm that uses a kind of separation of the conquest approach will reach a recursion depth of about 21. This means that even a smart implementation must be combined with 200 bytes (about 4000/21) for memory overhead at each stage of the recursion.

It should be possible to implement almost every in-place sorting algorithm with this limitation. For instance:.

• quicksort
• heap sorting
• Sort insert
• bubble sorting (not recommended)

and others (also the merge sort option should be at the merge sort place ).

Answer 4

Two things, one cosmic complexity and the complexity of time. Since your question specifically set limits on space, I would say that it is better to approach the problem with the best worst complexity of space. it

• pyramidal sort
• Smooth sorting
• Bubbleble
• insertion sort
• sort by selection

If performance is a problem in your application, then in the HeapSort and SmoothSort sections above it is possible to improve performance.

MergeSort may not be applicable in this scenario due to the complexity of the space.

Answer 5

Yes, there is a problem: merge sorting has linear space complexity. This means that this requires a amount of memory proportional to the number of records you want to sort.

If your transactions are already in memory, then you may need an in situ (or in memory) algorithm such as quicksort or heapsort. Otherwise, you should use an algorithm that runs directly on disk, as suggested by @YoungHobbit.