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:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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 this link

12-6-1: Under what condition will a merge sort execute faster?




12-6-2: Which sort should be the fastest most of the time?