Sorting Correctness and Analysis Lab

P1. Inversions and stability

For (3,A),(1,B),(3,C),(2,D), trace insertion sort, count strict inversions, and show final tagged output. Prove why strict shifting preserves tie order. Then replace the comparison with a non-strict one and give the smallest failure.

P2. Partition contracts

Partition [2,1,2,3,2] into strict-low/equal/strict-high regions. Name all four loop regions and a termination measure. Explain the all-equal behavior of three-way quicksort versus two-way Lomuto with random pivot selection.

P3. Lower-bound assumptions

Show why sorting three distinct keys needs at least three comparisons in the worst case. Which part requires uniformly distributed inputs? Repeat the count of distinguishable key orders for multiset [1,1,2,2].

P4. Stable integer passes

Stable-count-sort (2,A),(0,B),(2,C),(1,D) with exclusive start offsets. Trace counts, offsets, and placements. Then trace two LSD passes over [21,12,11,22]. State time and storage in n, key range R, digit count d, and radix b as appropriate. Explain why choosing a larger radix cannot make fixed-width sorting sublinear.

Attempt independently, then consult Practice Solutions. Submit a proof or counterexample as requested; code output alone is insufficient.