# Sorting Strategies

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/sorting-strategies

## Why Sort?

**Sorting** arranges data into order, making searching, grouping, and deduplication trivial.

| Category | Complexity | Key Algorithms |
| --- | --- | --- |
| **Simple** | $O(n^2)$ | **Bubble**, **Selection**, **Insertion** |
| **Efficient** | $O(n \log n)$ | **Merge**, **Quicksort**, **Heapsort** |

- **Bubble sort**: swaps adjacent out-of-order elements.
- **Selection sort**: finds the smallest remaining element.
- **Insertion sort**: builds a sorted prefix, inserting new elements. **Fast on nearly-sorted or small inputs**.

## Efficient Sorts & Stability

- **Merge sort**: divides list in half, recurses, and **merges** sorted halves. Always $O(n \log n)$ and **stable**.
- **Quicksort**: partitions around a **pivot** ($O(n \log n)$ average, $O(n^2)$ worst case).
- **Heapsort**: extracts from a heap ($O(n \log n)$ guaranteed).

**Stability** preserves the relative order of equal elements. Merge sort is stable; Quicksort usually is not.

> **Pitfall:** $O(n \log n)$ is the comparison lower bound ($\Omega(n \log n)$). However, **Insertion sort** can beat efficient sorts on small inputs due to low overhead.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Order the steps of one round of selection sort.

**Answer:**

1. Scan the unsorted part to find the smallest remaining element
2. Swap it into the first unsorted position
3. Shrink the unsorted part by one
4. Repeat until the unsorted part is empty

**Why:** Find the smallest remaining element, put it next, shrink the unsorted region, and repeat. Placing before finding would be impossible, the minimum must be located first.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/order-the-steps-of-one-round-of-selection-sort

### 2. Stability in a sort, preserving the order of equal elements, sounds like a technicality. When does it become essential?

A. When sorting by successive keys, so earlier order survives
B. When the comparison function is expensive to evaluate
C. When the data contains duplicate values, which unstable sorts cannot handle
D. When sorting large datasets, where instability compounds

**Answer:** A. When sorting by successive keys, so earlier order survives

**Why:** Multi-key sorting is built on it: sort by the secondary key, then stably by the primary, and the earlier order survives inside each group. An unstable sort discards that work, which is why Python's sort is guaranteed stable and why spreadsheet sorting behaves the way users expect.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/stability-in-a-sort-preserving-the-order-of-equal-elements-sounds

### 3. Sorting stability only matters when the records carry information beyond the key being sorted on.

**Answer:** True

**Why:** True. Stability preserves the relative order of equal keys, which is observable only if those records differ in some other field. It is what makes multi-pass sorting work: sort by name, then stably by department, and equal departments stay in name order. Sorting bare integers, stability is undetectable.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/sorting-stability-only-matters-when-the-records-carry-information

### 4. Sort each sorting algorithm by its typical asymptotic cost.

**Answer:**

- Quadratic O(n^2): Bubble sort, Selection sort, Insertion sort
- Linearithmic O(n log n): Merge sort, Quicksort (average case), Heapsort

**Why:** Bubble, selection, and insertion are the simple O(n^2) sorts; merge, quicksort (on average), and heapsort are the efficient O(n log n) sorts real systems use for large data.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/sort-each-sorting-algorithm-by-its-typical-asymptotic-cost

### 5. Comparison-based sorting cannot beat O(n log n), and counting sort runs in O(n). Why is that not a contradiction?

A. Because counting sort never compares elements; it indexes by value.
B. Because counting sort is not a real sorting algorithm, since it does not produce a fully ordered result.
C. Because counting sort is O(n) only on already-sorted input, and O(n log n) otherwise.
D. Because the lower bound is a conjecture rather than a proved theorem.

**Answer:** A. Because counting sort never compares elements; it indexes by value.

**Why:** The theorem bounds *comparison*-based sorting, by a counting argument: n! orderings, one bit per comparison, so log₂(n!) ≈ n log n comparisons are needed. Counting sort never compares, it uses values as indices, which is more information than a comparison gives. The assumption is also the limitation: it needs bounded integer keys, and its cost is O(n + k) in the range.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/comparison-based-sorting-cannot-beat-o-n-log-n-and-counting-sort

### 6. Match each sort to its distinguishing property.

**Answer:**

- Merge sort → Always O(n log n) and stable
- Quicksort → Fast on average but O(n^2) with a bad pivot
- Insertion sort → Beats the fancy sorts on small or nearly-sorted inputs
- Heapsort → Guaranteed O(n log n), sorts in place

**Why:** Merge sort is stable and always O(n log n); quicksort is fast but has an O(n^2) worst case; insertion sort wins on small or nearly-sorted data; heapsort guarantees O(n log n) in place.

Page: https://tryals.app/practice/computer-science-i/sorting-strategies/match-each-sort-to-its-distinguishing-property