Introduction to Sorting Algorithms

In computer science, sorting is the process of arranging data into a specific order, such as numerical (1, 2, 3...) or alphabetical (A, B, C...). Whether you are looking at a leaderboard in a video game or searching for a contact on your phone, sorting is happening behind the scenes to make that data useful.

In this chapter, we will explore three specific sorting algorithms required by the AP curriculum: Selection Sort, Insertion Sort, and Merge Sort. Don't worry if these sound complex; we will break them down using everyday analogies like sorting a deck of cards!

Note: This chapter focuses on how these algorithms work. For details on how searching works or the mechanics of recursion, see the "Searching Algorithms" and "Recursion" chapters in this unit.

1. Selection Sort

The core idea of Selection Sort is that you "select" the smallest remaining item in the list and move it to the front.

How it Works (Step-by-Step)

  1. Start at the beginning of the array.
  2. Search through the entire unsorted portion to find the minimum value.
  3. Swap that minimum value with the value at the current starting position.
  4. Move the starting position one spot to the right and repeat until the whole array is sorted.

An Everyday Analogy

Imagine you have a row of five students of different heights. You walk down the line to find the shortest person. Once you find them, you have them swap places with the person standing at the very first spot. Now, the first spot is "sorted." You then look at the remaining four people to find the next shortest, and swap them into the second spot. You keep doing this until everyone is in order.

Informal Run-Time Analysis

Because you have to scan the remaining unsorted elements over and over, Selection Sort uses nested loops (a loop inside a loop). If you have \( n \) elements, the number of times the inner statement executes is roughly proportional to \( n^2 \). This makes it slow for very large data sets.

Key Takeaway: Selection Sort always performs the same number of comparisons regardless of whether the array is already partially sorted. It "selects" the smallest and swaps.

2. Insertion Sort

Insertion Sort works by taking one element at a time and "inserting" it into its correct position relative to the elements already looked at. This creates a "sorted side" and an "unsorted side."

How it Works (Step-by-Step)

  1. Start with the second element (the first element is "sorted" by itself).
  2. Compare this element to the one before it. If it's smaller, shift the previous element to the right.
  3. Continue shifting elements to the right until you find the correct "hole" for your current element.
  4. Insert the element into that spot.
  5. Move to the next unsorted element and repeat.

An Everyday Analogy

Think of how you sort a hand of playing cards. You pick up one card at a time. You look at the cards already in your hand and slide the new card into the exact right spot so that the cards in your hand stay in order. You are inserting the card where it belongs.

Informal Run-Time Analysis

Like Selection Sort, Insertion Sort uses nested loops, so for a random list of \( n \) elements, the work is proportional to \( n^2 \). However, Insertion Sort is very efficient for lists that are already mostly sorted. If the list is already in order, it barely has to do any shifting!

Key Takeaway: Insertion Sort "inserts" the current item into the sorted portion. It can be faster than Selection Sort if the data is already nearly in order.

Quick Review: Selection vs. Insertion
  • Selection Sort: Finds the smallest and swaps it into place. Constant number of comparisons.
  • Insertion Sort: Takes the next item and slides it into the correct spot. Fewer shifts if the list is already sorted.

3. Merge Sort

Merge Sort is a "Divide and Conquer" algorithm. Unlike the previous two, Merge Sort is recursive. It breaks the problem into tiny pieces, solves them, and puts them back together.

How it Works (Step-by-Step)

  1. Divide: Split the array in half.
  2. Conquer (Recursion): Keep splitting those halves until you have several "lists" that only contain one element. (A list with one element is technically already sorted!)
  3. Merge: Combine the small sorted lists back together into larger sorted lists until the entire array is reunited.

The Merge Process

The "magic" happens during the merge. Imagine you have two stacks of cards that are already sorted. To merge them into one sorted stack, you just look at the top card of each pile, take the smaller one, and place it into a new pile. You repeat this until both piles are empty.

Informal Run-Time Analysis

Merge Sort is significantly faster than Selection or Insertion sort for large data sets. While Selection and Insertion sort are proportional to \( n^2 \), Merge Sort's execution count is proportional to \( n \cdot \text{log}(n) \).

Example: If you have 100 items, \( n^2 \) is 10,000 operations, but Merge Sort would only take roughly 700 operations.

Key Takeaway: Merge Sort is recursive and much more efficient for large amounts of data, though it requires more memory because it creates temporary arrays during the merging process.

4. Comparing the Three Algorithms

When you see code on the AP Exam, look for these "fingerprints" to identify the algorithm:

1. Selection Sort Identification:

  • Look for two nested for loops.
  • Look for a variable often named min or minIndex.
  • Look for a single swap occurring at the end of the outer loop.

2. Insertion Sort Identification:

  • Look for an outer for loop and an inner while loop.
  • Look for a "temp" variable holding the value to be inserted.
  • Look for a while loop condition like j >= 0 && array[j] > temp (this is the "shifting" part).

3. Merge Sort Identification:

  • Look for recursion (the method calls itself).
  • Look for a "base case" that checks if the list size is less than 2.
  • Look for a call to a merge helper method that combines two smaller arrays.
Did You Know?

In Java, the ArrayList class doesn't have a built-in .sort() method that you need to know for the exam, but you will often be asked to write these algorithms specifically to sort an ArrayList or an Array. When sorting an ArrayList, remember to use .get(), .set(), and .size() instead of [] and .length!

Common Mistakes to Avoid

  • Off-by-One Errors: In Selection Sort, the outer loop usually runs to length - 1 because the last element will already be sorted by the time you reach it.
  • Incorrect Swapping: Remember that swapping two values requires a temporary variable. If you write a = b; b = a;, both variables will end up with the same value!
  • Merge Sort Memory: Remember that Merge Sort is recursive. If you see a method that doesn't call itself, it isn't Merge Sort!

Summary Table

Selection Sort: Best for simple implementation; \( n^2 \) performance; swaps once per outer loop.
Insertion Sort: Best for nearly sorted data; \( n^2 \) performance (but faster in practice for small lists).
Merge Sort: Best for large data sets; most efficient performance; uses recursion and extra memory.