Sorting problem has a variety of interesting algorithmic solutions that embody many Computer Science ideas:
- Comparison versus non-comparison based strategies,
- Iterative versus Recursive implementation,
- Divide-and-Conquer paradigm (e.g., Merge Sort or Quick Sort),
- Best/Worst/Average-case Time Complexity analysis,
- Randomized Algorithms
Sortability
What do we need to be able to sort a set of data?
We don’t need an integer mapping for each object. Rather, we just need to be able to compare any two given elements.
For standard sorting algorithms, we actually need more than just a partial order—we need a total order (also called a linear order). The key difference:
- A partial order allows some elements to be incomparable (like set inclusion: {1,2} and {2,3} are incomparable)
- A total order requires that every pair of distinct elements be comparable
The total order must satisfy:
- Antisymmetry: if a ≤ b and b ≤ a, then a = b
- Transitivity: if a ≤ b and b ≤ c, then a ≤ c
- Totality: for any a and b, either a ≤ b or b ≤ a (or both if equal)
Standard sorting algorithms (quicksort, mergesort, heapsort, etc.) assume a total order because they need to be able to compare any two elements they encounter.
This is the foundation of the comparison-based sorting model. Here, sorting is performed through a comparator function that takes two elements and returns their relative order (less than, equal to, or greater than). The elements themselves can be anything—the algorithm only "sees" them through the comparator.
Such sorting algorithms have cannot be made faster than \(O(n \log n)\) and the associated binary tree insertion cannot get better than \(O(\log n)\).
However, there different sorting models we can use other than this. These include:
- Non-Comparison Model (Distribution Sorts): These algorithms do not rely on comparing elements, but rather on properties of the data (like bit values or ranges). These models can break the \(\Omega (n \log n)\) barrier, often achieving linear time complexity \(O(n)\).
Examples: Counting Sort, Radix Sort, Bucket Sort.
- Sorting Networks Model: A theoretical model for parallel computation. It is composed of "wires" and "comparators" that operate simultaneously. The structure is fixed and does not depend on the input values, making it highly efficient for hardware implementation.
Examples: Bitonic Sorting Network.
Algorithms
| Sorting Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Short Description |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) | Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Larger elements "bubble" to the end. The invariant is that the last n elements are sorted after n outer loops. |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) | Divides the list into a sorted and unsorted part. It repeatedly finds the minimum element from the unsorted part and puts it at the beginning of the sorted part. |
| Insertion Sort | O(n) | O(n2) [binary insertion sort does not reduce time complexity] | O(n2) | O(1) | Builds the final sorted array one item at a time. It iterates through the input elements and inserts each element into its correct position in the already sorted part of the array. |
| Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | A divide-and-conquer algorithm that recursively divides the array into halves until single elements are left, then merges those halves in a sorted manner. |
| Quick Sort | O(nlogn) | O(nlogn) | O(n2) | O(logn) (average) / O(n) (worst) | A divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the picked pivot, then recursively sorts the sub-arrays. |
| Untitled | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | A comparison-based sorting technique based on binary heap data structure. It builds a max-heap (or min-heap) and repeatedly extracts the maximum (or minimum) element. |
| Counting Sort | O(n+c) | O(n+c) | O(n+c) | O(n) | Counting Sort sorts integers by counting occurrences of each value and reconstructing the sorted array, achieving linear time when the range is small. |
Sorting Stability
Informally, stability talks about the relative ordering between two identically valued items and whether it is preserved after the sorting algorithm is done.
If an algorithm always guarantees that the initial relative ordering of identically valued items is always preserved, then the algorithm is considered stable. If no such guarantees hold, then the algorithm is considered unstable.
Here are the stability of the common sorting algorithms:
| Algorithm | Stable? | Reason |
|---|---|---|
| Bubble Sort | Yes | Only if the element on the right is strictly smaller does the swap happen. Thus, elements of the same value don’t get swapped. |
| Selection Sort | No | Selection sort works by repeatedly finding the minimum element from the unsorted portion and swapping it with the element at the current position. This swapping can move equal elements past each other, breaking stability (eg: [2,2,1] the first 2 is sent to the end in the first step) |
| Insertion Sort | Yes | No swap occurs if an element being moved to the left encounters an element of the same value. |
| Merge Sort | Yes | If in the merge step of merge sort, the 2 elements being compared in the left half vs. the right half are the same, as long as we always opt to take the left element, then the algorithm is stable. |
| Quick Sort | No | Quicksort with an in-place partitioning algorithm is not a stable sorting algorithm. Swapping elements across large distances can change the relative order of equal elements. |
Example Problems
- Multiple Sorts: A very common application of sorting stability is to sort the dataset by 2 fields. Apply the stable algorithm to ensure that the previous sorts have been factored in.
Note that sorts are not commutative. Changing the order of the sorts changes the grouping so be careful.