JMU
Merge Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
Merge Sort
A Pseudcode Implementation
    mergesort(a[])
    {
      if (a has two or more elements) {

        mergesort(left half of a);
        mergesort(right half of a);

        merge(left and right halves of a);
      }
    }
  
An Example

Sorting the six-element array (8, 4, 7, 3, 9, 3)

images/mergesort.gif
Efficiency Analysis
Efficiency Analysis (cont.)
Efficiency Analysis (cont.)
An Implementation
cppexamples/sorting/MergeSort.cpp
        /**
 * Merges two halves of a subarray.
 *
 * Side Effects: The arrays is sorted in place
 *
 * @param a      The array containing the subarray
 * @param first  The index of the first element of the subarray
 * @param last   The index of the last element of the subarray
 */
void merge(int a[], int first, int last) {
  int i, j, k, middle, n, start, stop;
  int *temp;

  if (first >= last)
    return;

  // Allocate temporary storage
  temp = new int[last - first + 1];

  // Divide the subarray in half
  middle = (first + last) / 2;
  i = 0;
  j = first;
  k = middle + 1;

  // Put the elements of the halves (which are assumed to be
  // sorted) in temp in the proper order
  while ((j <= middle) && (k <= last)) {
    if (a[j] < a[k]) {
      temp[i] = a[j];
      i++;
      j++;
    } else {
      temp[i] = a[k];
      i++;
      k++;
    }
  }

  // Since the two halves may not be the same size we need to
  // copy the remaining elements of the subarray into temp
  while (j <= middle) {
    temp[i] = a[j];
    i++;
    j++;
  }

  while (k <= last) {
    temp[i] = a[k];
    i++;
    k++;
  }

  // Copy the elements of temp into the subarray
  for (i = first; i <= last; i++) {
    a[i] = temp[i - first];
  }

  // Deallocate the temporary storage
  //
  delete[] temp;
}

/**
 * Does the actual work of the merge sort
 *
 * @param a      The array of integers
 * @param first  The index of the first element of the subarray
 * @param last   The index of the last element of the subarray
 *
 * @effects      The order of the elements in a is changed
 */
void mergesort(int a[], int first, int last) {
  int middle;

  if (first < last) {
    middle = (first + last) / 2;
    mergesort(a, first, middle);
    mergesort(a, middle + 1, last);

    merge(a, first, last);
  }
}

/**
 * Sort an array of integers using a merge sort
 *
 * The array is sorted  "in place"
 *
 * @param a        The array of integers
 * @param length   The number of elements in the array
 *
 * @effects        The order of the elements in a is changed
 */
void sort(int a[], int length) {
  mergesort(a, 0, length - 1);
}
        
Nerd Humor
http://imgs.xkcd.com/comics/ineffective_sorts.png
(Courtesy of xkcd)