Sorting Algorithms
Quick, merge, heap, counting, radix; time/space tradeoffs.
Comparison sorts
Quick, merge, heap; lower bound n log n.
SORTING = arranging elements in a specific order (usually ascending).
(See Pack 12 for comparison-sorts; Pack 15 for non-comparison-sorts.)
COMPLETE SORTING ALGORITHM TABLE:
| Algorithm | Best | Avg | Worst | Space | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble | n | n² | n² | 1 | Yes | Yes |
| Selection | n² | n² | n² | 1 | No | Yes |
| Insertion | n | n² | n² | 1 | Yes | Yes |
| Merge | n log n | n log n | n log n | n | Yes | No |
| Quick | n log n | n log n | n² | log n | No | Yes |
| Heap | n log n | n log n | n log n | 1 | No | Yes |
| Counting | n+k | n+k | n+k | n+k | Yes | No |
| Radix | d(n+k) | d(n+k) | d(n+k) | n+k | Yes | No |
| Bucket | n+k | n+k | n² | n+k | Yes | No |
| Shell | n | depends | n^(3/2) | 1 | No | Yes |
| Tim | n | n log n | n log n | n | Yes | No |
| Intro | n log n | n log n | n log n | log n | No | Yes |
WHEN TO USE WHICH:
| Situation | Best Choice |
|---|---|
| Small array (n < 30) | Insertion |
| General purpose, in-place needed | Quick (with random pivot) or Heap |
| Stable required, can use extra memory | Merge |
| External sorting (data > RAM) | Merge |
| Linked list | Merge |
| Integers in range [0, k] | Counting |
| Integers with d digits | Radix |
| Nearly sorted | Insertion |
| Need O(n log n) guarantee | Merge or Heap |
| Real-world Python sorting | Tim (built-in) |
| Real-world Java Arrays.sort (primitives) | Dual-Pivot Quick |
| Java Arrays.sort (objects) | Tim |
KEY INSIGHTS:
1. Comparison lower bound: Ω(n log n) for comparison-based sorts.
2. Non-comparison sorts (counting, radix, bucket) can achieve O(n) for specific input types.
3. Stability matters when:
- Sorting by multiple criteria.
- E.g., sort by department, then by name within department.
4. In-place matters for:
- Memory-constrained environments.
- Embedded systems.
ADVANCED ALGORITHMS:
Tim Sort:
- Hybrid of merge + insertion.
- Used by Python (sort()), Java (Arrays.sort for objects), Android.
- Designed for real-world data (partially sorted).
- O(n log n) worst case; O(n) for nearly-sorted.
Intro Sort:
- Hybrid of quicksort + heapsort.
- Falls back to heapsort if quick recursion depth exceeds threshold.
- O(n log n) guaranteed; faster than pure quicksort.
- Used by C++ std::sort.
Shell Sort:
- Generalization of insertion sort.
- Sort sublists separated by gaps; gaps shrink.
- Best gap sequence: O(n^(4/3)) or even O(n log² n).
- Not stable; in-place.
Smooth Sort:
- Achieves O(n) for sorted input; O(n log n) worst.
- Uses Leonardo heap (variant of binary heap).
PARALLEL & EXTERNAL SORTING:
External Merge Sort: when data > RAM.
- Read chunks; sort in memory; write back.
- Merge sorted chunks.
- Used in databases, big data.
Parallel sorts:
- Bitonic sort (good for parallel hardware).
- Sample sort (distributed).
- Map-reduce sort.
INTERESTING FACTS:
- Bogo sort: randomly shuffle until sorted. O(n × n!) expected. Joke algorithm.
- Stooge sort: recursive; O(n^2.71). Bad performance.
- Pancake sort: sort by reversing prefixes. NP-hard for "minimum pancake number" problem.
- Sleep sort: thread per element; each sleeps proportional to value. Linear time but impractical.
SORTING PROBLEMS:
Q1. Sort an array of 0s, 1s, 2s in O(n).
- Dutch national flag algorithm (3-way partition).
- O(n) time, O(1) space.
Q2. Find the kth smallest element in unsorted array.
- Quickselect: O(n) avg, O(n²) worst.
- Or: build min-heap (O(n)); extract k times (O(k log n)).
Q3. Sort array of strings.
- Compare strings character by character.
- For very long strings: radix sort by character.
Q4. Merge K sorted lists.
- Min-heap of K elements.
- Time: O(N log K), where N = total elements.
EXAM HOOKS:
- Comparison lower bound: Ω(n log n).
- Counting sort: O(n+k); only for integers in [0,k].
- Radix sort uses counting as stable digit sort.
- Merge sort is stable; quick is not.
- Quick sort worst case: O(n²) for sorted input.
- Heap sort: O(n log n), in-place.
- For small arrays: insertion sort wins.
Non-comparison sorts
Counting, radix, bucket sort.
SORTING = arranging elements in a specific order (usually ascending).
(See Pack 12 for comparison-sorts; Pack 15 for non-comparison-sorts.)
COMPLETE SORTING ALGORITHM TABLE:
| Algorithm | Best | Avg | Worst | Space | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble | n | n² | n² | 1 | Yes | Yes |
| Selection | n² | n² | n² | 1 | No | Yes |
| Insertion | n | n² | n² | 1 | Yes | Yes |
| Merge | n log n | n log n | n log n | n | Yes | No |
| Quick | n log n | n log n | n² | log n | No | Yes |
| Heap | n log n | n log n | n log n | 1 | No | Yes |
| Counting | n+k | n+k | n+k | n+k | Yes | No |
| Radix | d(n+k) | d(n+k) | d(n+k) | n+k | Yes | No |
| Bucket | n+k | n+k | n² | n+k | Yes | No |
| Shell | n | depends | n^(3/2) | 1 | No | Yes |
| Tim | n | n log n | n log n | n | Yes | No |
| Intro | n log n | n log n | n log n | log n | No | Yes |
WHEN TO USE WHICH:
| Situation | Best Choice |
|---|---|
| Small array (n < 30) | Insertion |
| General purpose, in-place needed | Quick (with random pivot) or Heap |
| Stable required, can use extra memory | Merge |
| External sorting (data > RAM) | Merge |
| Linked list | Merge |
| Integers in range [0, k] | Counting |
| Integers with d digits | Radix |
| Nearly sorted | Insertion |
| Need O(n log n) guarantee | Merge or Heap |
| Real-world Python sorting | Tim (built-in) |
| Real-world Java Arrays.sort (primitives) | Dual-Pivot Quick |
| Java Arrays.sort (objects) | Tim |
KEY INSIGHTS:
1. Comparison lower bound: Ω(n log n) for comparison-based sorts.
2. Non-comparison sorts (counting, radix, bucket) can achieve O(n) for specific input types.
3. Stability matters when:
- Sorting by multiple criteria.
- E.g., sort by department, then by name within department.
4. In-place matters for:
- Memory-constrained environments.
- Embedded systems.
ADVANCED ALGORITHMS:
Tim Sort:
- Hybrid of merge + insertion.
- Used by Python (sort()), Java (Arrays.sort for objects), Android.
- Designed for real-world data (partially sorted).
- O(n log n) worst case; O(n) for nearly-sorted.
Intro Sort:
- Hybrid of quicksort + heapsort.
- Falls back to heapsort if quick recursion depth exceeds threshold.
- O(n log n) guaranteed; faster than pure quicksort.
- Used by C++ std::sort.
Shell Sort:
- Generalization of insertion sort.
- Sort sublists separated by gaps; gaps shrink.
- Best gap sequence: O(n^(4/3)) or even O(n log² n).
- Not stable; in-place.
Smooth Sort:
- Achieves O(n) for sorted input; O(n log n) worst.
- Uses Leonardo heap (variant of binary heap).
PARALLEL & EXTERNAL SORTING:
External Merge Sort: when data > RAM.
- Read chunks; sort in memory; write back.
- Merge sorted chunks.
- Used in databases, big data.
Parallel sorts:
- Bitonic sort (good for parallel hardware).
- Sample sort (distributed).
- Map-reduce sort.
INTERESTING FACTS:
- Bogo sort: randomly shuffle until sorted. O(n × n!) expected. Joke algorithm.
- Stooge sort: recursive; O(n^2.71). Bad performance.
- Pancake sort: sort by reversing prefixes. NP-hard for "minimum pancake number" problem.
- Sleep sort: thread per element; each sleeps proportional to value. Linear time but impractical.
SORTING PROBLEMS:
Q1. Sort an array of 0s, 1s, 2s in O(n).
- Dutch national flag algorithm (3-way partition).
- O(n) time, O(1) space.
Q2. Find the kth smallest element in unsorted array.
- Quickselect: O(n) avg, O(n²) worst.
- Or: build min-heap (O(n)); extract k times (O(k log n)).
Q3. Sort array of strings.
- Compare strings character by character.
- For very long strings: radix sort by character.
Q4. Merge K sorted lists.
- Min-heap of K elements.
- Time: O(N log K), where N = total elements.
EXAM HOOKS:
- Comparison lower bound: Ω(n log n).
- Counting sort: O(n+k); only for integers in [0,k].
- Radix sort uses counting as stable digit sort.
- Merge sort is stable; quick is not.
- Quick sort worst case: O(n²) for sorted input.
- Heap sort: O(n log n), in-place.
- For small arrays: insertion sort wins.