Searching & Sorting
Merge, Quick & Counting Sort
Faster sorting: divide-and-conquer merge sort and quick sort with their partition traces, plus counting and radix sort that beat O(n log n) on integers.
The O(n²) sorts are fine for a few hundred elements. For a million, you need O(n log n). Both merge sort and quick sort get there with divide and conquer: split the problem, solve the pieces recursively, combine.
Merge sort
- Divide the array into two halves.
- Conquer: sort each half recursively.
- Combine: merge the two sorted halves (the two-pointer merge from the Arrays lesson).
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi) {
int tmp[64], i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (k = 0; k < hi - lo + 1; k++) a[lo + k] = tmp[k];
}
void mergeSort(int a[], int lo, int hi, int depth) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid, depth + 1);
mergeSort(a, mid + 1, hi, depth + 1);
merge(a, lo, mid, hi);
printf("%*smerged [%d..%d]: ", depth * 2, "", lo, hi);
for (int i = lo; i <= hi; i++) printf("%d ", a[i]);
printf("\n");
}
int main(void) {
int a[] = {38, 27, 43, 3, 9, 82, 10};
mergeSort(a, 0, 6, 0);
return 0;
} merged [0..1]: 27 38
merged [2..3]: 3 43
merged [0..3]: 3 27 38 43
merged [4..5]: 9 82
merged [4..6]: 9 10 82
merged [0..6]: 3 9 10 27 38 43 82Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n) in every case. The merge needs an O(n) temporary array. Merge sort is stable and is the standard choice for sorting linked lists and huge files on disk.
Quick sort
- Pick a pivot element.
- Partition: rearrange so everything smaller than the pivot is on its left and everything larger on its right. The pivot is now in its final position.
- Recursively sort the left and right parts. No merge step is needed.
The Lomuto partition uses the last element as the pivot:
#include <stdio.h>
void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(&a[++i], &a[j]); // grow the "smaller" region
swap(&a[i + 1], &a[hi]); // put the pivot between the regions
return i + 1;
}
void quickSort(int a[], int lo, int hi, int n) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
printf("pivot %2d -> index %d: ", a[p], p);
for (int i = 0; i < n; i++) printf(i == p ? "[%d] " : "%d ", a[i]);
printf("\n");
quickSort(a, lo, p - 1, n);
quickSort(a, p + 1, hi, n);
}
int main(void) {
int a[] = {10, 80, 30, 90, 40, 50, 70};
quickSort(a, 0, 6, 7);
return 0;
}pivot 70 -> index 4: 10 30 40 50 [70] 90 80 pivot 50 -> index 3: 10 30 40 [50] 70 90 80 pivot 40 -> index 2: 10 30 [40] 50 70 90 80 pivot 30 -> index 1: 10 [30] 40 50 70 90 80 pivot 80 -> index 5: 10 30 40 50 70 [80] 90
| Case | When | Cost |
|---|---|---|
| Best / average | pivot splits roughly in half | O(n log n) |
| Worst | pivot is always the smallest or largest (e.g. sorted input with last-element pivot) | O(n²) |
Choosing a random pivot or the median of three makes the worst case extremely unlikely. In practice quick sort is often the fastest comparison sort: it sorts in place (O(log n) stack space) and is cache-friendly. It is not stable.
Counting sort
When keys are small integers in a known range 0…k, you do not need comparisons at all. Count how many times each value occurs, then write the values out in order: O(n + k).
#include <stdio.h>
int main(void) {
int a[] = {4, 2, 2, 8, 3, 3, 1, 7, 2};
int n = 9, k = 8, count[9] = {0};
for (int i = 0; i < n; i++) count[a[i]]++;
int idx = 0;
for (int v = 0; v <= k; v++)
while (count[v]--) a[idx++] = v;
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}1 2 2 2 3 3 4 7 8
Radix sort applies a stable counting sort digit by digit (units, then tens, then hundreds…), sorting d-digit numbers in O(d × (n + 10)).
The big comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | no |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | no |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | yes |
Test yourself
4 questions · pick an answer to check it instantly
- 1
What is the worst-case time of merge sort?
Merge sort always splits in half and merges in linear time, whatever the input. - 2
When does quick sort with a last-element pivot hit its O(n²) worst case?
The pivot is then always the largest element, so each partition removes only one element. - 3
Which O(n log n) sort is stable?
Merge sort keeps equal elements in order if the merge takes from the left half on ties. - 4
Which algorithm sorts n integers in the range 0…k in O(n + k) time?
Counting sort tallies each value instead of comparing elements.