Sorting a Million Data…
During my job hunt, one of my interviewer asked me, how would you sort a million data?
I couldn’t answer right away, I kept using the sorting algorithms included in programming languages and libraries that I totally forgot the basics that all I answered was
“If I am going to sort a million data, I will not do it in the mobile phone but instead use a server to sort it for me.”
That look on the interviewer’s face says it all.
I need to refresh my basic concepts…
What is a Sorting Algorithm?
A sorting algorithm rearranges elements in a particular order. A sorting algorithm has the following properties
Stable: A sorting algorithm is said to be stable if it maintains the arrangement of the similar elements in input to the output.
Adaptive: An adaptive sorting algorithm has the ability to mark already sorted elements and will not try to rearrange it. An adaptive sorting algorithm has a best case time complexity of O(n).
Time Complexity: Amount of time the sorting algorithm needs in order to complete. Time complexity is broken down into worst case, average case and best case.
Space Complexity: Extra memory needed by the sorting algorithm to arrange the given elements.
The ideal sorting algorithm must be…
Up until now, there is no sorting algorithm that has the ideal property of a sorting algorithm. If there is, sorting algorithm wouldn’t be fun at all.
Different Sorting Algorithms
Below are the most common sorting algorithms and its properties…
When to use each sorting algorithm?
Q: Is the order of the same element important?
Yes: Insertion, Bubble, Merge, Quick
No: Heap, Quick
Q: Is the data size small?
Yes: Insertion, Bubble
No: Heap, Merge, Quick
Q: Is memory for extra space an issue?
Yes: Insertion, Bubble, Heap
No: Merge, Quick*
Q: Is the input data nearly sorted?
Yes: Insertion, Bubble
No: Heap, Merge, Quick
Q: Is speed important?
Yes: Heap, Merge, Quick
No: Insertion, Bubble
We now have three choices in order to sort one million data — Heapsort, Merge Sort and Quicksort. Choosing the appropriate sorting algorithm will still depend if order of the same element is important and memory for extra space is not an issue.
In depth discussion of the sorting algorithms above soon!
References:
Sorting Algorithms
Brilliant Math & Science Wiki
Sorting Algorithm Animations
Toptal
Data Structure — Sorting Techniques
Tutorials Point
