- Forward


Merge Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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
Merge Sort
Back SMYC Forward
  • 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
A Pseudcode Implementation
Back SMYC Forward
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
Back SMYC Forward

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

mergesort
Efficiency Analysis
Back SMYC Forward
  • 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)
Efficiency Analysis (cont.)
Back SMYC Forward
  • 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 \)
Efficiency Analysis (cont.)
Back SMYC Forward
  • 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)\)
An Implementation
Back SMYC Forward
cppexamples/sorting/MergeSort.cpp
 
Nerd Humor
Back SMYC Forward
/imgs
(Courtesy of xkcd)
There's Always More to Learn
Back -