Skip to main content

Sorting Correctness and Analysis Lab

Retrieval Prompts​

  1. State the loop invariant for insertion sort in one sentence.
  2. Write the recurrence for mergesort and its closed form.
  3. Describe the partition step of quicksort in your own words.
  4. State the Omega(n log n) comparison-sort lower bound and name the structure used to prove it.
  5. Give the exact condition that makes counting sort stable.
  6. Give two concrete situations in which insertion sort outperforms mergesort.

Compare and Distinguish​

Separate these pairs clearly -- a one-sentence answer on each:

  • worst case O(n log n) (mergesort, heapsort) vs expected O(n log n) (randomized quicksort)
  • stable sort vs in-place sort (they are orthogonal)
  • Omega(n log n) lower bound on comparisons vs the linear time of counting/radix sort
  • "nearly sorted" adaptivity of insertion sort vs best-case analysis of mergesort
  • LSD vs MSD radix sort
  • mergesort's Theta(n) auxiliary memory vs quicksort's Theta(log n) stack depth

Common Mistake Check​

For each statement, identify the error:

  1. "Randomized quicksort has worst-case O(n log n) because the pivot is random."
  2. "Counting sort violates the Omega(n log n) lower bound."
  3. "Since heapsort is O(n log n) in the worst case, it is faster than quicksort in practice."
  4. "Mergesort is in-place because it sorts a single array."
  5. "A sort is stable as long as it is deterministic."
  6. "Radix sort is always linear."

Mini Application -- Trace and Analyze​

Do each of the following:

  1. Trace insertion sort, mergesort, and quicksort (Lomuto partition with pivot = last element) on A = [5, 2, 8, 1, 9, 3, 7, 4, 6]. Show the array after each outer iteration (insertion), each merge (mergesort), and each partition (quicksort).

  2. For the mergesort recurrence T(n) = 2 T(n/2) + Theta(n), prove T(n) = Theta(n log n) by the recursion tree method: label each level, sum the level costs, confirm the geometry.

  3. Derive the expected number of comparisons for randomized quicksort on n distinct keys. (Hint: let X_{ij} be the indicator that elements at rank i and rank j are ever compared; use linearity of expectation.)

  4. Demonstrate that counting sort is stable by running it on [(3, 'a'), (1, 'x'), (3, 'b'), (2, 'y'), (1, 'z')] sorted by the integer key. Write the output and confirm that (3,'a') precedes (3,'b') and (1,'x') precedes (1,'z').

  5. Draw the decision tree for any comparison sort on three elements a, b, c. Count the leaves, measure the tree height, and confirm it is at least ceil(log2 6) = 3.

Analysis Drills​

For each algorithm, write:

  • best case, average case, worst case (in asymptotic notation)
  • in-place? (yes / no / with caveats)
  • stable? (yes / no / depends)
  • one situation where it is the right choice
  • one situation where it is the wrong choice

Algorithms: insertion sort, selection sort, bubble sort, mergesort, quicksort (random pivot), heapsort, counting sort, radix sort, introsort, Timsort.

Evidence Check​

This page is complete only if you can:

  • state and use a loop invariant to justify a sort's correctness
  • derive a recurrence from a divide-and-conquer sort and solve it
  • distinguish stability, in-place, and worst-case guarantees as three independent axes
  • name which sort your default language sort() actually runs and why