Sorting Algorithms to Know for AP Computer Science A

What You Need to Know

Sorting is a classic AP CSA topic because it tests your ability to trace loops, reason about array/index behavior, and compare algorithm efficiency.

On the AP Computer Science A exam, the “big three” sorting algorithms to know are:

• Selection Sort
• Insertion Sort
• Merge Sort

You should be able to:

• Describe what each sort does in plain English.
• Trace a few iterations/passes on an array.
• Identify time complexity (best/average/worst) using $O(\cdot)$ notation.
• Know key properties: in-place vs extra memory, stable vs unstable.
• Apply comparisons for primitives and objects (using Comparable / compareTo).

AP CSA vibe: You’re rarely asked to invent a new sort from scratch, but you are often asked to predict intermediate states or explain why a given implementation works.

Core definitions (must-know vocabulary)

• Sorted (ascending): for all adjacent indices $k$, $a[k] \le a[k+1]$.
• In-place: uses only $O(1)$ extra memory (besides a few variables).
• Stable sort: if two items are “equal” by the comparison, their relative order stays the same after sorting.
• Comparison sort: sorting by comparing elements (all three here are comparison sorts).

Comparable comparisons in Java

• For primitives like $int$, you compare with $$.
• For objects (like $String$), typical AP style uses:
  • x.compareTo(y)
  • Negative means $x < y$, zero means equal, positive means $x > y$.

Step-by-Step Breakdown

Below are “exam-traceable” versions of each algorithm. Focus on what becomes sorted after each outer loop / recursion level.

1) Selection Sort (repeat: find min, swap into place)

Idea: Build a sorted prefix from left to right. On pass $i$, find the minimum in the unsorted suffix $[i..n-1]$ and swap it into index $i$.

Steps (array length $n$):

1. For $i = 0$ to $n-2$:
2. Set $minIndex = i$.
3. For $j = i+1$ to $n-1$:
   • If $a[j] < a[minIndex]$, set $minIndex = j$.
4. Swap $a[i]$ with $a[minIndex]$.
5. After pass $i$, indices $0..i$ are sorted and finalized.

Mini trace example: sort [5, 2, 4, 1]

• Pass $i=0$: min is $1$ at index $3$ → swap with index $0$ → [1, 2, 4, 5]
• Pass $i=1$: min of suffix [2,4,5] is already at $1$ → no change

Key decision point: selection sort does one swap per outer pass, after scanning.

2) Insertion Sort (repeat: insert current into sorted left side)

Idea: Treat the left side as a sorted “hand of cards.” Take the next element (the “key”) and shift larger elements right until you can insert the key.

Steps:

1. For $i = 1$ to $n-1$:
2. Set $key = a[i]$, $j = i-1$.
3. While $j \ge 0$ and $a[j] > key$:
   • Shift right: $a[j+1] = a[j]$
   • Decrement: $j--$
4. Place key: $a[j+1] = key$
5. After iteration $i$, indices $0..i$ are sorted.

Mini trace example: sort [5, 2, 4, 1]

• $i=1$, key=2: shift 5 right → [5,5,4,1], insert 2 → [2,5,4,1]
• $i=2$, key=4: shift 5 → [2,5,5,1], insert 4 → [2,4,5,1]
• $i=3$, key=1: shift 5,4,2 → insert 1 → [1,2,4,5]

Key decision point: insertion sort’s inner loop does shifts, not repeated swaps (though swap-based versions exist).

3) Merge Sort (divide, sort halves, merge)

Idea: Recursively split the array into halves until size $1$, then merge sorted halves back together.

High-level steps:

1. Split array segment $[low..high]$ at $mid$.
2. Recursively merge sort $[low..mid]$.
3. Recursively merge sort $[mid+1..high]$.
4. Merge the two sorted halves into one sorted segment.

Typical recursion base case:

• If $low \ge high$, return (segment length $\le 1$ is already sorted).

Merging procedure (two pointers):

• You have sorted left half $[low..mid]$ and sorted right half $[mid+1..high]$.
• Use pointers $i$ (left), $j$ (right), and $k$ (temp array index).
• Repeatedly copy the smaller of $a[i]$ and $a[j]$ into temp.
• Copy any leftovers from left or right.
• Copy temp back into $a[low..high]$.

Tiny merge example: merging [2,5] and [1,4]

• Compare 2 vs 1 → take 1
• Compare 2 vs 4 → take 2
• Compare 5 vs 4 → take 4
• Leftover 5 → take 5
• Result: [1,2,4,5]

Critical reminder: merge sort’s speed comes from merging in linear time after splitting.

Key Formulas, Rules & Facts

Complexity + properties (the big comparison table)

When each one is “the right mental model”

Loop bounds you should memorize (common AP implementations)

• Selection sort
  • Outer: $i = 0$ to $n-2$
  • Inner: $j = i+1$ to $n-1$
• Insertion sort
  • Outer: $i = 1$ to $n-1$
  • Inner while: $j \ge 0$ and out-of-order condition
• Merge sort
  • Base case: $low \ge high$
  • Midpoint: often $mid = (low + high) / 2$ (integer division)

Stability details (subtle but testable)

• Insertion sort is stable if you only shift items when $a[j] > key$ (strictly greater). If you shift on $\ge$, you can break stability.
• Merge sort is stable if when equal, you take from the left half first.
• Selection sort is usually unstable because swapping the min into place can move equal items past each other.

Comparing objects (AP CSA style)

• For ascending order using compareTo:
  • “Out of order” check: arr[j].compareTo(key) > 0
• For descending order:
  • Flip the comparison direction.

Examples & Applications

Example 1: Identify which algorithm matches the behavior

Array state changes:

• Start: [4, 1, 3, 2]
• After pass 1: [1, 4, 3, 2]
• After pass 2: [1, 2, 3, 4]

Key insight: After pass 1, the smallest element is in position 0. After pass 2, the second smallest is in position 1. That’s classic selection sort behavior (min-search + swap each pass).

Example 2: Insertion sort intermediate state question

Start [2, 5, 4, 6, 1]

• After $i=2$ (inserting element at index 2):
  • Left prefix becomes sorted: [2, 4, 5, 6, 1]

Key insight: insertion sort ensures the prefix $[0..i]$ is sorted after each outer iteration.

Example 3: Merge sort split/merge reasoning

Given [8, 3, 7, 4]:

• Split into [8,3] and [7,4]
• Sort halves → [3,8] and [4,7]
• Merge → [3,4,7,8]

Key insight: merge sort’s “magic step” is merging two sorted lists in linear time.

Example 4: Sorting objects with compareTo

If you have String[] words = {"bat", "apple", "cat"};

• Lexicographic order uses compareTo.
• Sorted result: ["apple", "bat", "cat"]

Key insight: you don’t use $<$ with objects; you use compareTo and check sign.

Common Mistakes & Traps

1. Off-by-one in selection sort loops

   • Wrong: running outer loop to $n-1$ or inner loop starting at $i$.
   • Why wrong: redundant comparisons or missing needed comparisons.
   • Fix: outer $i = 0..n-2$, inner $j = i+1..n-1$.

2. Swapping inside the inner loop in selection sort

   • Wrong: swapping every time you see a new minimum.
   • Why wrong: it can still sort, but it’s no longer the standard selection sort trace and complicates intermediate states.
   • Fix: track $minIndex$ during inner scan; do one swap at the end.

3. Insertion sort: forgetting to save the key

   • Wrong: shifting overwrites a[i] before you store it.
   • Why wrong: you lose the value you’re trying to insert.
   • Fix: store key = a[i] before shifting.

4. Insertion sort: placing the key at the wrong index

   • Wrong: doing a[j] = key after the loop.
   • Why wrong: when the loop stops, $j$ is at the last index that is $\le$ key (or $-1$), so the correct position is $j+1$.
   • Fix: always assign a[j + 1] = key.

5. Merge sort: incorrect base case

   • Wrong: using something like if (low == high) return; but then splitting can skip or loop incorrectly with certain mid calculations.
   • Why wrong: for safety, you want to stop for any segment of length $\le 1$.
   • Fix: if (low >= high) return;.

6. Merge step: not copying leftovers

   • Wrong: after the main merge loop ends, not copying remaining elements from one half.
   • Why wrong: you drop values and the result is missing elements.
   • Fix: after merging while both halves have elements, copy remaining left half, then remaining right half.

7. Stability misunderstandings

   • Wrong: assuming all sorts are stable or that stability “doesn’t matter.”
   • Why wrong: stability can affect results when sorting objects by one key then another.
   • Fix: remember: insertion/merge are stable (typical), selection usually isn’t.

8. Using $==$ to compare objects

   • Wrong: if (a[j] == key) or using $<$ on objects.
   • Why wrong: $==$ compares references, not ordering.
   • Fix: use compareTo (or equals for equality checks only).

Memory Aids & Quick Tricks

Quick Review Checklist

• You can explain and trace selection, insertion, and merge sort.
• You know what’s sorted after each step:
  • Selection: position $i$ finalized each pass.
  • Insertion: prefix $[0..i]$ sorted each iteration.
  • Merge: after merge, that subarray segment sorted.
• You know time complexities:
  • Selection: $O(n^2)$ always.
  • Insertion: best $O(n)$, worst $O(n^2)$.
  • Merge: $O(n\log n)$ always (typical).
• You know space/stability:
  • Selection: in-place, usually unstable.
  • Insertion: in-place, stable (shifting version).
  • Merge: $O(n)$ extra, stable (typical merge).
• You can compare objects correctly using compareTo.
• You avoid classic indexing mistakes: loop bounds, $j+1$ insertion, copying merge leftovers.

You’ve got this—if you can trace these three cleanly, you’re in great shape for AP CSA sorting questions.