BrewlearnMerge sort & quicksort in Java
Divide and conquer, stability, worst cases.
Divide and conquer
Merge sort: split the array in half, sort each half recursively, then merge the two sorted halves. Halving gives log n levels, and each level does n work merging, so it's O(n log n) every time: best, average and worst case.
The merge step
Merging compares the heads of two sorted halves and takes the smaller each time. Using <= means ties take from the left half first, so equal elements keep their order: merge sort is stable. When one half runs out, copy whatever is left of the other.
while (i < l.length && j < r.length)
out[k++] = l[i] <= r[j]
? l[i++] : r[j++];
// then copy whatever is left overDon't forget the leftovers
What does this print?
int[] l = {2, 5}, r = {1, 3, 9};
int[] out = new int[5];
int i = 0, j = 0, k = 0;
while (i < l.length && j < r.length)
out[k++] = l[i] <= r[j] ? l[i++] : r[j++];
while (i < l.length) out[k++] = l[i++];
while (j < r.length) out[k++] = r[j++];
System.out.println(Arrays.toString(out));[1, 2, 3, 5, 9][1, 2, 3, 5, 0][2, 5, 1, 3, 9]
Show the answer
Round 1: 2 vs 1, take 1. Round 2: 2 vs 3, take 2. Round 3: 5 vs 3, take 3. Round 4: 5 vs 9, take 5. Now l is exhausted and the first loop stops; the leftover loop copies 9. Without it, the last slot would stay 0.
Quicksort: partition around a pivot
Quicksort picks a pivot, moves smaller items to its left and larger to its right, then recurses on each side. It sorts in place and is very fast in practice: O(n log n) on average, with a typical recursion depth of O(log n). It is not stable.
The sorted-input disaster
Always picking the first element as pivot is fine on shuffled data. On already sorted input the pivot is always the smallest, so each partition splits into 0 and n - 1 items. That's n levels of about n work: O(n²). Random or median-of-three pivots make this very unlikely.
Merge or quick?
When would you choose merge sort over quicksort?
Think about it, then reveal the answer
When you need stability or a guaranteed O(n log n) worst case, and can spare O(n) extra memory. Quicksort's worst case is O(n²), but it's in place and usually faster for primitives, where stability doesn't matter.
Choosing in real systems
Merge sort's guarantees make it the backbone of Java's object sort, and of external sorting when data is bigger than memory. Quicksort variants dominate primitive sorting. Interviewers expect you to compare their worst cases, extra space and stability.
Key takeaways
- Merge sort: guaranteed O(n log n), stable, O(n) extra memory
- Quicksort: fast in practice, in place, not stable
- First-element pivot on sorted input gives O(n²)
- Random or median-of-three pivots make that very unlikely
💡 Merge sort is two people each sorting half a deck, then dealing the two piles together.
John von Neumann described merge sort in 1945. Tony Hoare invented quicksort in 1959 while working on machine translation as a visiting student in Moscow.
Practice questions
What does this print?
int[] l = {1, 4, 9}, r = {2, 3, 10};
int[] out = new int[6];
int i = 0, j = 0, k = 0;
while (i < 3 && j < 3)
out[k++] = l[i] <= r[j] ? l[i++] : r[j++];
IO.println(k + " " + Arrays.toString(out));- 5 [1, 2, 3, 4, 9, 0]
- 6 [1, 2, 3, 4, 9, 10]
- 5 [1, 2, 3, 4, 9, 10]
- 4 [1, 2, 3, 4, 0, 0]
Check your answer
5 [1, 2, 3, 4, 9, 0]. The loop takes the smaller head each time: 1, 2, 3, 4, 9. Then l is exhausted and the loop stops, leaving 10 uncopied and the last slot at 0.
Which input makes quicksort with 'always pick the first element as the pivot' degrade to O(n²)?
- A randomly shuffled array
- An array of distinct primes
- An already sorted array
- An array of length 1
Check your answer
An already sorted array. On sorted input the first element is the smallest, so every partition splits into 0 and n - 1 elements.