This book is now obsolete Please use CSAwesome instead.

13.6. Merge Sort¶

A merge sort recursively breaks the values to be sorted in half until there is only one value to be sorted and then it merges the two sorted lists into one sorted list. The code shown below uses a second array the same size as the original array for merging the values in order. Then it copies all of the sorted values back into the original array.

Here is a folk dance video that shows the merge sort process.

To identify a merge sort look for the following:

3 methods, mergeSort, mergeSortHelper, and merge
mergeSortHelper is recursive

The code for mergeSort below is from the AP CS A course description.

import java.util.Arrays;

public class SortTest
{
   public static void mergeSort(int[] elements)
   {
      int n = elements.length;
      int[] temp = new int[n];
      mergeSortHelper(elements, 0, n - 1, temp);
   }

private static void mergeSortHelper(int[] elements,
                                       int from, int to, int[] temp)
   {
       if (from < to)
       {
          int middle = (from + to) / 2;
          mergeSortHelper(elements, from, middle, temp);
          mergeSortHelper(elements, middle + 1, to, temp);
          merge(elements, from, middle, to, temp);
       }
   }

private static void merge(int[] elements, int from,
                             int mid, int to, int[] temp)
   {
      int i = from;
      int j = mid + 1;
      int k = from;

while (i <= mid && j <= to)
      {
         if (elements[i] < elements[j])
         {
            temp[k] = elements[i];
            i++;
         }
         else
         {
            temp[k] = elements[j];
            j++;
         }
         k++;
      }

while (i <= mid)
      {
         temp[k] = elements[i];
         i++;
         k++;
      }

while (j <= to)
      {
         temp[k] = elements[j];
         j++;
         k++;
      }

for (k = from; k <= to; k++)
      {
         elements[k] = temp[k];
      }
   }

public static void main(String[] args)
   {
      int[] arr1 = {86, 3, 43};
      System.out.println(Arrays.toString(arr1));
      mergeSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}

To see this executing using the Java Visualizer click on the following Merge-Sort

13-6-3: Under what condition will a merge sort execute faster?

If the data is already sorted in ascending order
This won't really affect the execution time for merge sort.
If the data is already sorted in descending order
This won't really affect the execution time for merge sort.
It will always take the same amount of time to execute
It will take about the same time regardless of the data.

13-6-4: Which sort should be the fastest most of the time?

selection sort
Selection sort always takes about the same time. Merge sort is always more effecient than selection sort.
insertion sort
Merge sort is usually faster than insertion sort.
merge sort
Merge sort is always faster than selection sort and usually faster than insertion sort.

You have attempted of activities on this page