Content

Merge Sort Basics Top-down Merge Sort (Recursive) Top-down Merge Sort Advantages & Disadvantages Bottom-up Merge Sort <- Go Back

EECS 281: Data Structures and Algorithms

Section 11

Merge Sort

University of Michigan at Ann Arbor

Last Edit Date: 06/14/2023

Disclaimer and Term of Use:

1. We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

2. This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

Merge Sort Basics

Different from quick sort, which divides a file into two parts (k smallest elements, n - k largest elements), merge sort combines two ordered files to make one larger ordered file.

i. Comparing Quick Sort to Merge Sort

Algorithm quicksort(array)
    partition(array)
    quicksort(lefthalf)
    quicksort(righthalf)

Algorithm mergesort(array)
    mergesort(lefthalf)
    mergesort(righthalf)
    merge(lefthalf, righthalf)

• Much in common

• Top-down approach

  • Divide work

  • Combine work

• Nothing gets done until recursive calls get work done

ii. Important Concerns for Sorting

External Sort

• File to be sorted is on tape or disk

• Items are accessed sequentially or in large blocks

Memory Efficiency

• Sort in place with no extra memory

• Sort in place, but have poiniters to or indices (n items need an additional n poniters or indices)

• Need enough extra memory for an additional copy of items to be sorted

iii. Merging Sorted Ranges

 1     void mergeAB(Item c[], Item a[], size_t size_a, Item b[], size_t size_b) {
 2         size_t i = 0, j = 0;
 3         for (size_t k = 0; k < size_a + size_b; k++) {
 4             if (i == size_a)
 5                 c[k] = b[j++];
 6             else if (j == size_b)
 7                 c[k] = a[i++];
 8             else
 9                 c[k] = (a[i] <= b[j]) ? a[i++] : b[j++];
10         }
11     }

• Append smallest remaining item from a or b onto c until all items are in c

• $\Theta(\text{size_a} + \text{size_b})$ time for both arrays and linked list

Example:

Top-down Merge Sort (Recursive)

i. Code

 1     void mergesort(Item a[], size_t left, size_t right) {
 2         if (right < left + 2)
 3             return;
 4         size_t mid = left + (right - left);
 5         mergesort(a, left, mid);                      // [left, mid)
 6         mergesort(a, mid, right);                     // [mid, right)
 7         merge(a, left, mid, right);
 8     }

• Prototypical "combine and conquer" algorithm

• Recursively call until sorting array of size 0 or 1

• Then merge sorted lists larger and larger

 1     void merge(Item a[], size_t left, size_t mid, size_t right) {
 2         size_t n = right - left;
 3         vector<Item> c(n);
 4         for (size_t i = left, j = mid, l = 0; k < n; k++) {
 5             if (i == mid)
 6                 c[k] = a[j++];
 7             else if (j == right)
 8                 c[k] = a[i++];
 9             else
10                 c[k] = (a[i] <= a[j]) ? a[i++] : a[j++];
11         }
12         copy(begin(c), end(c), &a[left]);
13     }

Top-down Merge Sort Advantages & Disadvantages

Advantages (compare to quick sort)

• Fast: $O(n \log n)$

• Stable when a stable merge is used (it is always used)

• Normally implemented to access data sequentially

  • Does not require random access

  • Great for linked lists, external-memory and parallel sorting

Disadvantages

• Best case performance $\Omega(n \log n)$ is slower than some elementary sorts

  • Insensitive to input

• $\Theta(n)$ additional memory, while quick sort is in-place

  • Also extra data movement to / from copy

• Slower than quick sort on typical inputs

Bottom-up Merge Sort

 1     void merge_sortBU(Item a[], size_t left, size_t right) {
 2         for (size_t size = 1; size <= right - left; size *= 2)
 3             for (size_t i = left; i <= right - size; i += 2 * size)
 4                 merge(a, i, i + size; std::min(i + 2 * size, right));
 5     }

Prototypical "combine and conquer" algorithm

• View original file as n ordered sublists of size 1

• Perform 1-by-1 merges to produce n / 2 ordered sublists

• Perform 2-by-2 merges to produce n / 4 ordered sublists

• ...

© Sample Academy