Quick sort and merge sort
Quick sort and merge sort: definitions, divide-and-conquer ideas, partitioning/merging, time–space complexity, stability, in-place behavior, recurrences, Python implementations with sample I/O, exam-ready derivations and diagrams in words.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Software engineers frequently sort data: logs by timestamp, records by keys, and intermediate lists inside algorithms like searching, graph algorithms, and database operations. Knowing Quick sort and Merge sort helps you choose the correct method for speed, memory limits, and whether the original order of equal items (stability) must be preserved.
Key ideas
- Key: The value used to compare elements during sorting.
- Stable sort: A sorting algorithm is stable if equal-key elements appear in the output in the same relative order as in the input.
- In-place algorithm: An algorithm that uses O(1) additional auxiliary space beyond the input array, not counting recursion stack unless stated. (Some textbooks count recursion stack; we will state both when relevant.)
- Divide and Conquer: Design technique with three steps: Divide the problem into subproblems, Conquer by solving subproblems (usually recursively), and Combine their results.
Core idea of Quick sort:
- Quick sort (Quicksort) is a divide-and-conquer algorithm that picks a pivot element, partitions the array into two parts (elements less than pivot and elements greater than pivot; equals can be grouped with either side as chosen), and then recursively sorts the parts. Combine step is trivial because, in schemes like Lomuto, partitioning places the pivot in its final position (Hoare’s scheme returns a partition index; the pivot may not be at that index).
- Partition: Reorder the subarray so that every element on the left of the pivot is ≤ pivot and every element on the right is ≥ pivot (exact invariant depends on the chosen partition scheme). Common schemes:
- Lomuto partition: Uses last element as pivot; maintains an index i of the “≤ pivot” region and scans with j; swaps to expand the ≤ region.
- Hoare partition: Uses two indices that move inward and swap when out of place; often fewer swaps and works well with in-place property; pivot may not end up in its final place after partition; but subarray boundaries returned are such that recursive calls will sort correctly.
Core idea of Merge sort:
- Merge sort is a divide-and-conquer algorithm that splits the array into two equal halves, recursively sorts each half, then merges the two sorted halves into a single sorted array using a linear-time merge procedure.
- Merge: Given two sorted lists L and R, repeatedly choose the smaller front element to append to the output; if equal, take from L first to preserve stability.
Exact statements (exam-ready):
Definition — Quick sort: “Quick sort is a divide-and-conquer sorting algorithm that partitions an array about a pivot so that elements on one side are ≤ pivot and on the other are ≥ pivot, places the pivot in its correct sorted position, and then recursively sorts the subarrays.” Assumptions: elements are comparable by a total order; comparisons are consistent and transitive. Note: In Hoare’s partition scheme the pivot may not be in its final position after partition; the returned subarray boundaries still ensure correctness.
Definition — Merge sort: “Merge sort is a divide-and-conquer sorting algorithm that recursively sorts two halves of the array and then merges the two sorted halves into one sorted array.” Assumptions: elements are comparable by a total order; a merge procedure is available that can compare and move elements.
Stability: “Merge sort is stable when the merge procedure prefers the left element on ties. Standard quick sort with in-place partitioning is not stable.” Assumption: comparisons treat equal keys as equal; implementation does not perform extra steps to preserve original order for equal keys.
In-place property: “Standard quick sort with in-place partitioning requires O(1) auxiliary space plus recursion stack; merge sort needs Θ(n) auxiliary space for the merge (for arrays).” Note: Linked-list merge sort can be done in-place with O(1) extra pointers beyond recursion stack, but typical array-based merge sort uses an auxiliary array of size n.
Time complexity laws (comparison model):
- Quick sort: Best case Θ(n log n) when partitions are balanced; Average case Θ(n log n) for random pivots or random input permutations; Worst case Θ(n²) when partitions are highly unbalanced (e.g., already sorted input with poor pivot choice like first/last element). Assumptions: Distinct keys or random pivot selection; comparisons take O(1) time.
- Merge sort: Θ(n log n) in best, average, and worst cases. Assumptions: n = power of 2 often used in derivation; general n gives ceiling/floor rounding but same Θ. Note: In the comparison model, any sorting algorithm needs Ω(n log n) comparisons in the worst case; thus Θ(n log n) is asymptotically optimal.
Recurrence relations and derivations universities commonly expect:
- Merge sort recurrence: T(n) = 2·T(n/2) + Θ(n), with base T(1) = Θ(1). By substitution or Master Theorem (a = 2, b = 2, f(n) = Θ(n) = Θ(n^(log_b a) · log^0 n)), we get T(n) = Θ(n log n).
- Quick sort recurrence (balanced): T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n). Worst-case: T(n) = T(n−1) + Θ(n) ⇒ Θ(n²). Average-case: T(n) = (1/n)·∑{k=0}^{n−1} [T(k) + T(n−1−k)] + Θ(n) ⇒ Θ(n log n) after solving the harmonic-number form; detailed derivation uses induction and the identity ∑{k=1}^{n} H_k = (n+1)H_n − n, where H_n is the nth harmonic number.
Stability vs partition details: A standard Lomuto or Hoare partition does swaps that break the input relative order of equal keys, so quick sort is not stable without extra bookkeeping. The merge process can maintain order by taking from the left half on equal keys, hence merge sort is stable.
What to draw in diagrams (describe and label):
- Partition diagram for Quick sort: Draw a horizontal array box, index positions 0…n−1 on top. Mark pivot element with a distinct label (e.g., “pivot = A[high]”). Show regions: [≤ pivot] region from low to i, [unknown] scanning region from i+1 to j−1, [unprocessed] from j to high−1, and pivot at high. Arrows show j moving left-to-right and swaps when A[j] ≤ pivot expand the ≤ region.
- Recursion tree for Merge sort: Draw a binary tree with root labeled size n, splitting into n/2 and n/2 on the next level, until leaves of size 1. Next to each level, note “work at level = n” for merging cost. At the bottom write “number of levels = log₂ n”, total work = n · log₂ n.
- Merge diagram: Two rows for L and R (both sorted), with front pointers i and j. A third row for Output, where you append min(L[i], R[j]). On ties, draw an arrow from L to Output before R to indicate stability.
Engineering choice guidance:
- If you need guaranteed O(n log n) and stability: prefer Merge sort (or TimSort in practice; Python’s built-in sort is stable).
- If you need in-place with low extra memory and typically fast average performance: Quick sort with good pivot selection (randomized or median-of-three) works well but watch worst case and lack of stability.
Formulas
- T_merge(n): time to sort n items with merge sort (unit: steps or comparisons; abstract). Applies to array-based merge sort; c is a constant cost per element to merge.
T_quick_best(n) = 2·T_quick_best(n/2) + c·n- Balanced partitions yield this; solution Θ(n log n).
T_quick_worst(n) = T_quick_worst(n−1) + c·n- Highly unbalanced partition (e.g., pivot is min or max). Solution Θ(n²).
Average(T_quick(n)) = Θ(n log n)- For random pivot or random permutation of distinct keys under the comparison model.
- Syntax to remember (Python-like pseudocode):
- Partition (Lomuto):
pivot = A[high]; i = low - 1; for j in range(low, high): if A[j] <= pivot: i += 1; swap A[i], A[j]; swap A[i+1], A[high]; return i+1 - Quick sort:
qs(A, low, high): if low < high: p = partition(A, low, high); qs(A, low, p-1); qs(A, p+1, high) - Merge:
while i < len(L) and j < len(R): if L[i] <= R[j]: out.append(L[i]); i += 1; else: out.append(R[j]); j += 1; append remaining - Merge sort:
ms(A): if len(A) <= 1: return A; mid = n//2; L = ms(A[:mid]); R = ms(A[mid:]); return merge(L, R)
- Partition (Lomuto):
Worked examples
Example 1: Quick sort (Lomuto partition), integers
Python program:
# Quick sort using Lomuto partition scheme
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
def quick_sort(arr, low=None, high=None):
if low is None or high is None:
low, high = 0, len(arr) - 1
if low < high:
p = partition(arr, low, high)
quick_sort(arr, low, p - 1)
quick_sort(arr, p + 1, high)
if __name__ == "__main__":
data = [29, 10, 14, 37, 13, 13, 5, 3]
print("Input:", data)
quick_sort(data)
print("Sorted:", data)
Sample run (exact output):
Input: [29, 10, 14, 37, 13, 13, 5, 3]
Sorted: [3, 5, 10, 13, 13, 14, 29, 37]
Notes: Pivot is always the last element of the current subarray. This implementation is not stable. Average-case time is Θ(n log n); worst-case is Θ(n²) for already-sorted or reverse-sorted arrays with this pivot choice.
Example 2: Stable Merge sort on records (key, tag)
Goal: Show stability by preserving the relative order of equal keys.
Python program:
# Stable merge sort for a list of (key, tag) pairs, sorting by key only
def merge(left, right):
i = j = 0
out = []
while i < len(left) and j < len(right):
if left[i][0] <= right[j][0]: # take from left on tie → stable
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
def merge_sort(records):
n = len(records)
if n <= 1:
return records
mid = n // 2
left = merge_sort(records[:mid])
right = merge_sort(records[mid:])
return merge(left, right)
if __name__ == "__main__":
data = [(20, 'A'), (10, 'X'), (20, 'B'), (10, 'Y'), (30, 'Z')]
print("Input:", data)
sorted_data = merge_sort(data)
print("Sorted:", sorted_data)
Sample run (exact output):
Input: [(20, 'A'), (10, 'X'), (20, 'B'), (10, 'Y'), (30, 'Z')]
Sorted: [(10, 'X'), (10, 'Y'), (20, 'A'), (20, 'B'), (30, 'Z')]
Explanation: Among key 10, the order X before Y is preserved; among key 20, A before B is preserved. Thus the implementation is stable.
Example 3: Theory — Derive average-case time of Quick sort is Θ(n log n) (model answer)
- Assumptions: Distinct keys; pivot is chosen uniformly at random among the n elements, or input is a random permutation; cost counted in key comparisons.
- Let T(n) be the expected number of comparisons on an input of size n. Condition on the pivot’s rank k (0-based number of elements smaller than the pivot). With probability 1/n, k = 0,1,…,n−1. Then the sizes of subproblems are k and n−k−1.
- Recurrence: T(n) = (1/n)·∑_{k=0}^{n−1} [T(k) + T(n−k−1)] + (n−1), with base T(0) = T(1) = 0. The term (n−1) is the cost to partition once (comparing each of the other elements to the pivot once, up to constant factors).
- Observe symmetry: ∑{k=0}^{n−1} T(k) = ∑{k=0}^{n−1} T(n−k−1), so T(n) = (2/n)·∑_{k=0}^{n−1} T(k) + (n−1).
- Standard technique (telescoping with differences) or induction using harmonic numbers yields: T(n) = 2(n+1)H_n − 4n, where H_n = 1 + 1/2 + … + 1/n. Since H_n = Θ(log n), T(n) = Θ(n log n).
- Conclusion: Expected time of randomized quick sort is Θ(n log n); worst-case time remains Θ(n²) for an adversarial pivot sequence.
Common mistakes
- Forgetting to state assumptions (random pivot or random input) when claiming average-case Θ(n log n) for Quick sort.
- Confusing in-place property: Saying “Merge sort is in-place for arrays” (typical array merge sort uses Θ(n) extra space; only linked-list merge sort can be done with O(1) extra pointers).
- Incorrect partition boundaries: Off-by-one errors in Lomuto/Hoare partition, leading to infinite recursion or missing elements.
- Choosing poor pivot but still claiming Θ(n log n) without caveats; using first/last element pivot on already sorted input causes Θ(n²).
- Not preserving stability in merge: Using
<instead of<=in merge and then incorrectly claiming stability still holds. - Not mentioning recursion depth/stack: Quick sort’s recursion depth can be Θ(n) in worst case; average is Θ(log n) with random pivots.
For your exam
- Short notes: Compare Quick sort vs Merge sort (time, space, stability, typical use-cases). Mention average/worst time and extra space.
- Derivations: Solve recurrences for Merge sort using Master Theorem; show expected time of Quick sort using the pivot-rank recurrence and harmonic numbers.
- Programs: Implement Quick sort (Lomuto or Hoare) and Merge sort in a chosen language (Python/C/Java). Show sample input/output. Mention whether the implementation is stable and in-place.
- Diagrams: Partition trace for Quick sort, recursion tree for Merge sort, merge operation step-by-step. Label indices, pivot, and regions clearly.
- Edge cases: Duplicates; already sorted input; reverse-sorted input; choice of pivot strategies (median-of-three, randomization). State effect on performance and stability.
- Complexity table (to write in words):
- Quick sort: Best Θ(n log n), Average Θ(n log n), Worst Θ(n²), Space O(1) auxiliary + recursion; not stable.
- Merge sort: Θ(n log n) in all cases, Space Θ(n) auxiliary (arrays); stable.
- Marks boosters: State conditions for Master Theorem, show each step, and justify stability decisions (<= in merge). Mention recursion depth and stack space briefly.
Quick check
- State whether Quick sort and Merge sort are stable and in-place for arrays.
- Write the recurrence of Merge sort and solve it to Θ-notation.
- Why can Quick sort degrade to Θ(n²) time, and how can you reduce that risk?
Answers: 1) Quick sort: not stable, in-place (O(1) auxiliary) plus recursion stack; Merge sort: stable, not in-place (needs Θ(n) auxiliary space). 2) T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n). 3) Highly unbalanced partitions from bad pivot choices (e.g., first/last pivot on sorted input); use randomized pivot or median-of-three and limit recursion depth.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?