Sorting

INS — Insertion Sort

solved Problem statement

The swap count is the number of inversions, so the same loop answers INV as well. Sorts in place, which the index assignment added for these packs is what makes possible.

MER — Merge Two Sorted Arrays

solved Problem statement

MS — Merge Sort

solved Problem statement

PAR — 2-Way Partition

solved Problem statement

Any valid partition is accepted, so the three conditions are asserted rather than one arrangement.

HS — Heap Sort

solved Problem statement

INV — Counting Inversions

solved Problem statement

Counted during the merge rather than pairwise, so this is n log n where INS's swap count is quadratic. The two problems ask for the same number.

PAR3 — 3-Way Partition

solved Problem statement

Dutch national flag. Any valid arrangement is accepted, so the three regions are asserted rather than one output; this one happens to match the sample.

PS — Partial Sort

solved Problem statement

QS — Quick Sort

solved Problem statement