Solution to merge sort practice problem

Complete the Merge sort practice problem before viewing the solution.

Review the merge sort practice problem with AP CS Tutor Brandon Horn.

Merge sort implementation

When presented for academic purposes, merge sort is usually implemented recursively with code that closely resembles the algorithm itself. It is also easy to implement merge sort iteratively by sorting and merging increasingly longer portions of the array.

The solution below includes an implementation of merge which is not tested 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)
  {
    if (low < high)
    {
      int mid = (low + high) / 2;
      sort(a, low, mid);
      sort(a, mid + 1, high);
      merge(a, low, mid, high);
    }
  }

  /** 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)
  {
    int[] b = new int[mid + 1 - low];
    for(int i = 0; i < b.length; i++)
      b[i] = a[i + low];

    int aLowerIndex = low, bIndex = 0, aHigherIndex = mid + 1;
    while (aLowerIndex < aHigherIndex && aHigherIndex <= high)
    {
      if (a[aHigherIndex] < b[bIndex])
        a[aLowerIndex++] = a[aHigherIndex++];
      else
        a[aLowerIndex++] = b[bIndex++];
    }

    while (aLowerIndex < aHigherIndex)
      a[aLowerIndex++] = b[bIndex++];
  }
}

Get AP CS Help

Leave a Reply