Merge Sort in AP Computer Science A

In AP Computer Science A, merge sort is a recursive sorting algorithm that repeatedly divides an array or ArrayList into smaller subarrays until each has one element, then merges those sorted subarrays back together in order to form the final sorted collection (EK 4.17.C.2).

What is Merge Sort?

Merge sort is one of the three sorting algorithms you're responsible for in AP CSA, along with selection sort and insertion sort. It's the recursive one. Per EK 4.17.C.1, it can sort elements in an array or an ArrayList.

The algorithm runs in two phases. First it divides. It splits the collection in half, then splits each half in half, and keeps going until every piece is a single element. A one-element list is already sorted, so that's the base case. Then it merges. It takes two sorted pieces, compares their front elements, copies the smaller one into a new spot, and repeats until both pieces are used up. Those merged pieces get merged with their neighbors, level by level, until you're back to one fully sorted array. Think of it as "break it into the smallest possible problems, then glue the answers back together in order."

Why Merge Sort matters in AP® Computer Science A

Merge sort lives in Unit 4: Data Collections, Topic 4.17 Recursive Searching and Sorting. It directly supports learning objective AP Comp Sci A 4.17.C, which asks you to determine the result of each iteration of merge sort when it sorts a collection. It also leans on AP Comp Sci A 4.17.A (determining the result of recursive algorithms that use collections), because merge sort is recursion applied to arrays and ArrayLists.

This matters because merge sort is where the course's two big ideas, recursion and data collections, meet. If you can trace merge sort, you understand how recursive calls split a problem and how results come back up the call stack. The CED also draws a hard boundary. Sorting algorithms other than selection, insertion, and merge sort are outside the scope of the course and exam, so merge sort is the only recursive sort you need to know.

How Merge Sort connects across the course

Binary Search Algorithm (Unit 4)

Binary search and merge sort sit side by side in Topic 4.17, and both cut a collection in half each step. They need each other, too. Binary search only works on sorted data (EK 4.17.B.1), and merge sort is one way to get that data sorted in the first place.

Selection Sort and Insertion Sort (Unit 4)

These are merge sort's two in-scope siblings. Selection and insertion sort use nested loops and work through the list one position at a time. Merge sort uses recursion and divide-and-conquer instead. The CED caps sorting at these three, so comparing how each one changes the array is fair game.

Traverse (Unit 4)

EK 4.17.A.1 says recursion can traverse Strings, arrays, and ArrayLists. The merge step is a traversal of two sorted subarrays at once, with an index moving through each. If you can track those indices, you can trace any merge.

Linear Search (Unit 4)

Linear search checks elements one by one and works on unsorted data. Once a list is merge-sorted, you can switch to binary search, which is typically more efficient (EK 4.17.B.2). Sorting is the up-front cost that unlocks the faster search.

Is Merge Sort on the AP® Computer Science A exam?

Merge sort shows up mostly as tracing questions in multiple choice. The skill named in 4.17.C is to determine the result of each iteration, so you'll be handed a specific array and asked what happens at a certain moment. Typical stems look like these:

• "At what point will the subarray [1, 9] first be created?" when sorting [9, 1, 8, 2, 7, 3, 6, 4]
• "How many subarrays of size 1 exist after all divisions but before any merging?" (for 8 elements, the answer is 8)
• "How many total merge operations occur when sorting 8 elements?" (8 → 4 → 2 → 1 means 4 + 2 + 1 = 7 merges)
• "Which describes the pattern of merge operations?" (pairs merge first, then pairs of pairs, then the two halves)

You may also see a merge sort implementation in code and need to predict output or count calls. No released FRQ has used merge sort by name, but FRQs regularly test recursion and array/ArrayList traversal, which are exactly the skills merge sort relies on. The best prep is to draw the split tree and the merge tree by hand for an 8-element array until it feels automatic.

Merge Sort vs Binary search algorithm

Both split a collection in half, so they're easy to blur together. The difference is what happens to the halves. Binary search throws one half away each step because the target can't be there, and it ends by finding a value (or not). Merge sort keeps both halves, sorts each one, and merges them back, and it ends with a fully sorted array. Binary search also requires sorted data to start. Merge sort is what produces sorted data.

Key things to remember about Merge Sort

• Merge sort is a recursive sorting algorithm that works on both arrays and ArrayLists.

• Merge sort keeps dividing the collection in half until every subarray holds just one element, which is the base case because a single element is already sorted.

• During the merge step, the algorithm compares the front elements of two sorted subarrays and repeatedly takes the smaller one, building a combined sorted subarray.

• For an array of 8 elements, merge sort creates 8 one-element subarrays and performs 7 merge operations in total.

• Unlike binary search, which discards half the data each step, merge sort keeps and processes both halves.

• Selection, insertion, and merge sort are the only sorting algorithms in scope for the AP CSA exam, so quick sort, heap sort, and radix sort won't be tested.

Frequently asked questions about Merge Sort

What is merge sort in AP Computer Science A?

Merge sort is a recursive algorithm that splits an array or ArrayList into one-element subarrays and then merges them back together in sorted order. It's covered in Topic 4.17 under learning objective 4.17.C, where you trace each iteration of the sort.

How many merge operations does merge sort do on 8 elements?

It does 7 merges. The 8 single elements merge into 4 pairs (4 merges), those become 2 groups of four (2 merges), and those become 1 sorted array (1 merge), so 4 + 2 + 1 = 7.

Does merge sort sort the array while it's dividing it?

No. The dividing phase only splits the array until every piece has one element. All the actual ordering happens during the merge phase, when sorted pieces are combined.

How is merge sort different from binary search?

Binary search finds a value in already-sorted data by eliminating half the collection each step. Merge sort puts data in order by splitting it, keeping both halves, and merging them. One searches and the other sorts, but both appear in Topic 4.17.

Is quick sort or heap sort on the AP CSA exam?

No. The CED's exclusion statement limits sorting to selection, insertion, and merge sort, so quick sort, heap sort, and radix sort are outside the scope of the exam.