DSA: Sorting Algorithms
Understand every major sorting algorithm, when to use each, and the tradeoffs between stability, space, and speed.
Bubble Sort
Bubble sort repeatedly compares adjacent pairs and swaps them if out of order. The largest unsorted element bubbles to its correct position after each pass.
Bubble Sort
Simple to understand but inefficient for large inputs. Use only for educational purposes or tiny arrays.
- Time: O(n²) worst and average, O(n) best case with early-exit optimization
- Space: O(1) in-place
- Stable: equal elements never swap
- Early-exit: if no swaps occur in a full pass, the array is already sorted
Bubble Sort with Early Exit
C++The swapped flag detects an already-sorted array and exits in O(n) best case.
Selection Sort
Selection sort finds the minimum element in the unsorted portion and swaps it into the next sorted position. It always makes exactly n-1 swaps regardless of input.
Selection Sort
Minimizes swaps (n-1 total) but performs O(n²) comparisons in all cases.
- Time: O(n²) for all cases (always scans remaining unsorted portion)
- Space: O(1) in-place
- NOT stable: a swap can move an equal element past another
- Useful when write operations are costly, as it minimizes swaps
Selection Sort
C++Finds the minimum in each pass and places it. O(n²) time but only n-1 swaps total.
Insertion Sort
Insertion sort builds the sorted portion one element at a time by shifting elements rightward to make room for the current element, like sorting a hand of playing cards.
Insertion Sort
Excellent for small arrays or nearly-sorted data. It is the go-to for the base case in hybrid sorts like Timsort.
- Time: O(n²) worst, O(n) best (already sorted), O(n²) average
- Space: O(1) in-place
- Stable: shifting preserves relative order of equal elements
- Online: can sort a stream, processes one element at a time
Insertion Sort
C++Shifts elements right to open a slot for the current key. O(n) on nearly-sorted input.
Merge Sort
Merge sort divides the array in half, recursively sorts both halves, then merges them. It guarantees O(n log n) in all cases and is the foundation for external sorting.
Merge Sort
Divide and conquer. Guaranteed O(n log n) time at the cost of O(n) auxiliary space.
- Time: O(n log n) for all cases
- Space: O(n) auxiliary for the merge step
- Stable: merge preserves order of equal elements
- Preferred for linked lists and external sorting of large files
Merge Sort
C++Split, sort recursively, merge. O(n log n) guaranteed regardless of input order.
Count Inversions using Merge Sort
An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Merge sort counts all inversions in O(n log n) by counting cross-half inversions during the merge step.
Inversions via Merge Sort
When a left-half element is greater than a right-half element during merge, it forms (mid - i + 1) inversions at once.
- Brute force counts inversions in O(n²)
- Merge sort counts them in O(n log n) by leveraging sorted order during merge
- When arr[i] > arr[j] during merge: all remaining left elements also invert with arr[j]
- Inversion count measures how far an array is from being sorted
Count Inversions via Merge Sort
C++O(n log n). During merge, a left element greater than a right element accounts for multiple inversions at once.
Quick Sort
Quick sort picks a pivot, partitions the array into elements less than and greater than the pivot, then recurses on both sides. It is the fastest general-purpose sort in practice.
Quick Sort
Average O(n log n) in-place. Worst case O(n²) occurs with a bad pivot, mitigated by random pivot selection.
- Time: O(n log n) average, O(n²) worst (sorted array with first-element pivot)
- Space: O(log n) average stack depth (in-place partitioning)
- NOT stable: partition swaps can change relative order of equal elements
- Random pivot selection virtually eliminates the O(n²) worst case
Quick Sort with Random Pivot
C++Random pivot selection prevents the O(n²) worst case on already-sorted input.
Quick Select: Kth Smallest Element
Quick select reuses the partition step from quick sort but recurses on only one side, finding the kth smallest element in O(n) average time without fully sorting the array.
Quick Select
After partitioning, the pivot is in its final sorted position. Recurse only into the side that contains k.
- Time: O(n) average, O(n²) worst case
- Space: O(log n) average recursive stack
- Does NOT return a sorted array, only finds the kth order statistic
- Median of medians guarantees O(n) worst case but is rarely needed in practice
Quick Select: Kth Smallest
C++O(n) average. Recurses into only one side of the partition, unlike full quick sort.
Heap Sort
Heap sort builds a max-heap from the array in O(n), then repeatedly extracts the maximum to sort the array in O(n log n) total with O(1) extra space.
Heap Sort
Guaranteed O(n log n) with O(1) space. Not stable, and slower in practice than quick sort due to poor cache behavior.
- Time: O(n log n) for all cases
- Space: O(1) in-place (heapify in-place)
- NOT stable: heapify swaps disrupt relative order
- Used when both O(n log n) guarantee and O(1) space are required simultaneously
Heap Sort
C++Build max-heap in O(n), then extract-max n times. O(n log n) guaranteed, O(1) space.
Non-Comparison Sorts: Counting, Radix, Bucket
These algorithms sort without comparing elements directly. They exploit the structure of the values to achieve O(n) or O(n + k) time, breaking the O(n log n) lower bound of comparison sorts.
Non-Comparison Sorting
Faster than comparison sorts when the value range or structure is known, but require constraints on input.
- Counting Sort: count frequencies, O(n + k) where k is the value range
- Radix Sort: sort digit by digit from least to most significant, O(d × (n + k))
- Bucket Sort: distribute into buckets, sort each bucket, O(n) average for uniform data
- None work well on arbitrary large integers or floating-point data
Counting Sort
C++O(n + k). Counts element frequencies then reconstructs the sorted array. No comparisons needed.
Sorting Algorithm Comparison
No single sorting algorithm wins on every metric. The right choice depends on input size, data characteristics, memory constraints, and whether stability matters.
Stability and In-Place
Stable sorts keep equal elements in their original order. In-place sorts use O(1) auxiliary space.
- Stable and in-place: Insertion Sort, Bubble Sort
- Stable but not in-place: Merge Sort (needs O(n) auxiliary)
- In-place but not stable: Heap Sort, Quick Sort, Selection Sort
- std::sort in C++ uses Introsort (Quick + Heap + Insertion), O(n log n) guaranteed
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
Knowledge Check
1. Which sorting algorithm is stable AND in-place with O(n²) worst case?
2. What is the average-case time complexity of Quick Sort?
3. Which sorting algorithm is NOT comparison-based?
4. A sorting algorithm is "stable" if it:
5. What is the worst-case time complexity of Heap Sort?
6. Quick Select finds the kth smallest element in what average-case time?
7. Merge Sort requires O(n) extra space because:
8. Counting Sort is most efficient when: