• A Popular Motivation:
  • Between 25% and 50% of computing time in commercial applications is devoted to sorting
  • Hence, it is important to consider the efficiency of sorting algorithms
• My Motivation:
  • The issues that arise are illustrative of the issues that arise when developing other algorithms
  • They provide good examples of how to find the efficiency of an algorithm

• Approach:
  • The array is split in half, each half is sorted, and then the two halves are merged together
  • Of course, each half is sorted using the merge sort algorithm (i.e., each half is split, sorted and merged)
  • Thus, the merge sort algorithm is defined recursively
• Developed by:
  • John von Neumann

    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);
      }
    }
  

• Worst Case Time Efficiency: The Simple Case
  • An array with one element
  • \(T(1) = 0\)
• Worst Case Time Efficiency: Other Cases
  • Two calls to mergesort and one call to merge
  • Each call to mergesort has worst case efficiency of \(T(n/2)\)
  • The call to merge has worst case efficiency of \(n\) (to merge the two half arrays)

• Getting Started:
  • \(T(n) = 2 \cdot T(n/2) + n\)
• Applying the Recursion:
  • \(T(n/2) = 2 \cdot T(n/4) + n/2\)
• Substituting:
  • \(T(n) = 2 \cdot (2 \cdot T(n/4) + n/2) + n = 4 \cdot T(n/4) + 2 \cdot n/2 + n\)
• Applying the Recursion:
  • \(T(n/4) = 2 \cdot T(n/8) + n/4\)
• Substituting:
  • \(T(n) = 4 \cdot (2 \cdot T(n/8) + n/4) + 2 \cdot n/2 + n = 8 \cdot T(n/8) + 4 \cdot n/4 + 2 \cdot n/2 + n = 8 \cdot T(n/8) + 3 \cdot n \)

• Generalizing:
  • \(T(n) = 2^k \cdot T(n/(2^k)) + k \cdot n\) for any \(k\)
• Suppose \(k = \log_{2} n\):
  • By definition \(2^k = n\)
  • So \(T(n) = n \cdot T(1) + \log_2 n \cdot n = \log_2 n \cdot n = O(n \log n)\)
• An Observation::
  • \(O(n \log n)\) is considerably better than \(O(n^2)\)

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);
}