Merge sort is a recursive algorithm to arrange the elements of a data structure, such as an array or list, in increasing or decreasing order. The algorithm partitions the portion of the array into 2 unsorted halves, sorts each half, then merges the 2 sorted halves into 1 sorted whole.

On the AP Computer Science Exam, you must recognize the algorithm when it is presented in code.

## Merge sort implementation

Complete the private recursive helper method sort below. The method sorts a[low]…a[high] while leaving the rest of the array untouched. You may assume that method merge works as specified. The merge portion of merge sort is not covered on the AP Computer Science Exam.

public class MergeSort { public static void sort(int[] a) { sort(a, 0, a.length - 1); } private static void sort(int[] a, int low, int high) { /* to be completed */ } /** Precondition: a[low]...a[mid] is sorted && a[mid+1]...a[high] is sorted * Postcondition: a[low]...a[high] is sorted */ private static void merge(int[] a, int low, int mid, int high) { /* implementation not shown */ } }

See the Merge sort practice problem solution or review it with AP CS Tutor Brandon Horn.