Sorting algorithms
Problem¶
List sorting algorithms with their complexities, and the data structures that suit them.
Complexity and properties¶
Let:
- \(n\) be the number of elements.
- \(k\) be the integer-key range or number of buckets.
- \(d\) be the number of processed digits.
- \(b\) be the radix base.
| Algorithm | Best | Average | Worst | Auxiliary space | Stable |
|---|---|---|---|---|---|
| Bubble sort | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | Yes |
| Selection sort | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | No |
| Insertion sort | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | Yes |
| Shell sort | Depends on gaps | Depends on gaps | Usually \(O(n^2)\) | \(O(1)\) | No |
| Merge sort | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | Structure-dependent | Yes |
| Heap sort | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | No |
| Quicksort | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n^2)\) | Stack-dependent | No |
| Timsort | \(O(n)\) | \(O(n \log n)\) | \(O(n \log n)\) | Up to \(O(n)\) | Yes |
| Counting sort | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | Yes |
| LSD radix sort | \(O(d(n+b))\) | \(O(d(n+b))\) | \(O(d(n+b))\) | \(O(n+b)\) | Yes |
| Bucket sort | \(O(n+k)\) | \(O(n+k)\) expected | \(O(n^2)\) | \(O(n+k)\) | Depends |
Data-structure suitability¶
| Algorithm | Python list | Linked list | Notes |
|---|---|---|---|
| Bubble sort | Applicable but poor | Possible but awkward | Adjacent node swaps add complexity |
| Selection sort | Applicable but poor | Possible but poor | Repeated scans remain \(O(n^2)\) |
| Insertion sort | Good for nearly sorted data | Good | Relinking nodes costs \(O(1)\) |
| Shell sort | Appropriate | Inappropriate | Requires indexed access |
| Merge sort | Good | Excellent | Sequential merging suits linked lists |
| Heap sort | Excellent | Inappropriate | Heap indexing requires random access |
| Quicksort | Excellent | Usually inappropriate | Partitioning and tail access are awkward |
| Counting sort | Good for bounded integers | Usually convert/rebuild | Depends on values, not node structure |
| Radix sort | Good for suitable keys | Possible with bucket queues | More complex than merge sort |
| Bucket sort | Good for known distributions | Possible but uncommon | Usually implemented with arrays |
| Timsort | Preferred in Python | Convert or merge-sort directly | Python built-ins require a sequence/iterable |
Which algorithm to chose?¶
| Constraint | Appropriate choice |
|---|---|
| Normal Python program | Timsort through sorted or list.sort |
| Singly linked list | Merge sort |
| Nearly sorted small input | Insertion sort |
| Stable \(O(n \log n)\) sorting | Merge sort or Timsort |
| Guaranteed \(O(n \log n)\) and \(O(1)\) array space | Heap sort |
| Fast average array sorting | Randomized three-way quicksort |
| Many duplicate array values | Three-way quicksort |
| Small bounded integer range | Counting sort |
| Fixed-width integer or string keys | Radix sort |
| Uniform values in a known range | Bucket sort |
| Data larger than memory | External merge sort |
| Stable linked-list sort with \(O(1)\) auxiliary space | Bottom-up merge sort |
| Linked list with random-access algorithm | Avoid heap sort and Shell sort |
| Production Python code | Prefer built-in sorting |
Merge-sort space clarification¶
- Top-down array merge sort uses \(O(n)\) merge storage and \(O(\log n)\) recursion stack.
- Bottom-up array merge sort avoids recursion but normally still uses \(O(n)\) merge storage.
- Top-down linked-list merge sort uses \(O(\log n)\) recursion stack and \(O(1)\) node storage.
- Bottom-up linked-list merge sort uses \(O(1)\) auxiliary node storage.
- An \(O(1)\)-space stable merge for arrays exists, but it is complex and not the standard interview implementation.
Python Built-in sort¶
Python sorted (and .sort()) implements Timsort algorithms.
This algo exploits existing ordered runs, giving \(O(n)\) best-case and \(O(n \log n)\) worst-case time.