Sorting algorithms typically arrange a given sequence of elements in a specific order. The sorted order of elements could be ascending, descending or based on any given criteria. Merge Sort and Quick Sort are commonly used sorting algorithms.
Stable Sort : A sorting algorithm that maintains the relative order of elements of the same value (in the unsorted array) after sorting.
Below is the list of some known sorting algorithms along with their complexity.
| Algorithm | Main Idea | Stable | Time Complexity |
|---|---|---|---|
| Merge Sort | The array to be sorted is split all the way down to a single element using recursion before merging which occurs during the way out. It uses extra space for sorting. Thus it exhibits bottom-up recursion. | Yes | Best-case : O ( n log n ) Worst-case : O ( n log n ) Average-case : O ( n log n ) |
| Quick Sort | Quick Sort is an in-place sorting algorithm (no additional space required for sorting). Array partitioning and the main task of sorting happens before the recursive calls. Thus it exhibits top-down recursion. | No | Best-case : O ( n log n ) Worst-case : O ( n2 ) Average-case : O ( n log n ) |
GNU sort command on Linux which supports lexicographic and numeric ordering uses merge sort algorithm.