which sorting algorithm should be used for below scenario?

Question

The problem statement given is "You are working on an embedded device(an ATM) that only has 4 KB of free memory and you wish to sort the 2,000,000 transactions with-drawal history by the amount of money withdrawn (discarding the original order of transactions)."

For this problem statement , according to me we should use merge sort ,is there any issue with this sorting algorithm ?

Answer 1

You are definitely looking for an algorithm which space complexity is much less than O(n), since 2 millions transactions are likely to take much more than 4 KB...

space complexity gives the amount of memory space needed to perform the sort, with respect to the input size, in the worst case. With that low free memory, you cannot afford to use an algorithm taking much space.

Merge sort is space O(n), so you better look for something else.

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

Have a look at this table, which list

• Quick sort
• Bubble sort
• Heap sort
• Insertion sort
• and Shell sort

as being at most space O(log n).