01 / 22

Sorting
Algorithms

Master the fundamental sorting techniques in computer science: Selection Sort, Insertion Sort, and Merge Sort, including their performance analysis using Big-O notation.

AP Computer Science A

What Is Sorting?

Sorting is the process of rearranging elements in a collection into a specific order, typically ascending or descending. It is one of the most fundamental operations in computer science and underpins efficient searching, data analysis, and algorithm design.

Unsorted 38 12 27 5 Sort Sorted 5 12 27 38 Arrange elements in ascending order

Why Sorting Matters

Sorted data enables dramatically faster operations. Binary search runs in \( O(\log n) \) on sorted data versus \( O(n) \) for linear search. Many real-world systems depend on sorted data for performance.

★ Searching
Binary search requires sorted data to achieve \( O(\log n) \) performance.
★ Databases
Indexes keep data sorted for fast query results and range lookups.
★ Algorithms
Many algorithms (merge, median, dedup) assume sorted input as a precondition.

Big-O Notation: Measuring Efficiency

Big-O notation describes how an algorithm's running time grows as the input size \( n \) increases. We focus on the worst-case scenario and ignore constants and lower-order terms.

Input Size (n) Time \( O(n^2) \) \( O(n \log n) \) \( O(n) \) \( O(\log n) \)

Selection Sort: Find the Minimum

Selection Sort repeatedly finds the minimum element from the unsorted portion and swaps it into the correct position at the front. After each pass, one more element is in its final place.

1
Scan the unsorted portion to find the minimum element.
2
Swap the minimum with the first unsorted element.
3
Move the boundary of the sorted region one step right.
4
Repeat until the entire array is sorted.

Selection Sort: Visual Walkthrough

Start 38 27 43 3 9 Find min = 3, swap with 38 Pass 1 3 27 43 38 9 Find min = 9, swap with 27 Pass 2 3 9 43 38 27 Find min = 27, swap with 43 Pass 3 3 9 27 38 43 Find min = 38, already in place Done! 3 9 27 38 43

Insertion Sort: Build As You Go

Insertion Sort builds a sorted subarray from left to right. It takes each unsorted element and inserts it into its correct position within the already-sorted portion by shifting larger elements to the right.

1
Start from index 1 (element at index 0 is trivially sorted).
2
Store the current element as the "key" to insert.
3
Shift all sorted elements greater than the key one position right.
4
Place the key into the gap. Repeat for all elements.

Hold the next item while making room

An archivist holds one portrait card above a gap between four cards on a table.Holding a card aside makes room to shift neighboring cards. In insertion sort, saving the key before shifting protects the value that will be inserted.

Save the key before shifting

Three rows show key 5 held separately, 7 shifted right, and the completed array [2, 5, 7, 1, 8]. The first three entries form the sorted prefix.Starting from [2, 7, 5, 1, 8], save key 5 from index 2, shift 7 right, then insert 5 after 2. The dotted position marks the insertion gap; Java array assignments overwrite values rather than create an empty cell.Open full diagram

Insertion Sort: Step by Step

Start 38 27 43 3 9 key = 27, insert before 38 Pass 1 27 38 43 3 9 key = 43, no shift needed Pass 2 27 38 43 3 9 key = 3, shift all, insert at 0 Pass 3 3 27 38 43 9 key = 9, insert after 3 Done! 3 9 27 38 43

Merge Sort: Divide and Conquer

Merge Sort is a recursive, divide-and-conquer algorithm. It splits the array in half, recursively sorts each half, then merges the two sorted halves back together.

1
Divide: Split the array into two halves at the midpoint.
2
Conquer: Recursively sort each half (base case: arrays of size 1).
3
Merge: Combine the two sorted halves by comparing front elements and placing the smaller one first.

Merge Sort: Splitting and Merging

Divide Phase 38 27 43 3 9 38 27 43 3 9 38 27 43 3 9 38 27 Merge Phase 27 38 43 3 9 3 9 27 38 43

Selection vs Insertion Sort

Selection Sort
Finds the minimum element and swaps it into position. Always makes \( \frac{n(n-1)}{2} \) comparisons regardless of input order.
Insertion Sort
Shifts elements to insert each item into its correct position. Adapts to nearly-sorted data for best-case \( O(n) \).
Selection Sort Insertion Sort
Best Case \( O(n^2) \) \( O(n) \)
Worst Case \( O(n^2) \) \( O(n^2) \)
Mechanism Find min, swap Shift, insert
Adaptive? No Yes

How to Choose a Sorting Algorithm

1
Check the input size. For small arrays (\( n < 20 \)), any \( O(n^2) \) sort is fast enough.
2
Check if data is nearly sorted. Insertion Sort excels here with near \( O(n) \) performance.
3
For large or random data, choose Merge Sort for guaranteed \( O(n \log n) \) time.
4
Consider space. Merge Sort requires \( O(n) \) extra memory. Selection and Insertion Sort are in-place (\( O(1) \) extra).
5
On the AP exam, count comparisons and swaps when tracing through code. Know which loop structure each algorithm uses.

Worked Example: Selection Sort Code

public static void selectionSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx])
        minIdx = j;
    }
    // Swap arr[i] and arr[minIdx]
    int temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
  }
}

Worked Example: Insertion Sort Code

public static void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]; // shift right
      j--;
    }
    arr[j + 1] = key;
  }
}

Worked Example: Merge Sort Code

public static void mergeSort(int[] arr, int lo, int hi) {
  if (lo < hi) {
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
  }
}

private static void merge(int[] arr, int lo, int mid, int hi) {
  int[] temp = new int[hi - lo + 1];
  int i = lo, j = mid + 1, k = 0;
  while (i <= mid && j <= hi)
    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  while (i <= mid) temp[k++] = arr[i++];
  while (j <= hi) temp[k++] = arr[j++];
  // copy temp back into arr
  for (int t = 0; t < temp.length; t++)
    arr[lo + t] = temp[t];
}

Common Mistakes

✕ Off-by-One Bounds
Selection Sort outer loop runs to arr.length - 1, not arr.length. Insertion Sort starts at index 1, not 0.
✕ Confusing Swap vs Shift
Selection Sort swaps two elements. Insertion Sort shifts elements right and places the key. Mixing these up changes behavior.
✕ Forgetting Space Cost
Merge Sort is NOT in-place: it uses \( O(n) \) extra memory for the temp array. Don't claim it has \( O(1) \) space.

Algorithm Comparison Summary

Selection Insertion Merge
Best Case \( O(n^2) \) \( O(n) \) \( O(n \log n) \)
Average Case \( O(n^2) \) \( O(n^2) \) \( O(n \log n) \)
Worst Case \( O(n^2) \) \( O(n^2) \) \( O(n \log n) \)
Space \( O(1) \) \( O(1) \) \( O(n) \)
In-Place? Yes Yes No
Stable? No Yes Yes
Adaptive? No Yes No

Question 1 of 5

What is the worst-case time complexity of Selection Sort on an array of \( n \) elements?

Question 2 of 5

Which sorting algorithm has a best-case time complexity of \( O(n) \)?

Question 3 of 5

After one complete pass of the outer loop in Selection Sort on the array [5, 3, 8, 1, 4], what is the resulting array?

Question 4 of 5

Which of the following is a disadvantage of Merge Sort compared to Selection Sort and Insertion Sort?

Question 5 of 5

You need to sort a very large dataset (\( n = 1{,}000{,}000 \)) that is in completely random order. Which algorithm should you choose for the best performance?