Learning materials

Mergesort

On this page

Overview

Mergesort is a classic example of a divide-and-conquer algorithm invented by John von Neumann in 1945. Mergesort works by recursively dividing the unsorted list into halves until each sub-list consists of a single element (and is therefore considered sorted).It then merges these smaller lists in a way that they remain sorted, eventually producing a single sorted list.

Characteristics

Divide and conquer algorithm
Comparison based (general purpose)
Recursive or iterative
Out-of-place
- Requires additional memory
- Efficient for linked lists
Efficient for large data sets
Stable - relative order of equal elements is preserved
Parallelizable

Algorithm Details

Steps (top-down)
1. Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
2. Conquer: Sort the two subsequences recursively using merge sort.
3. Combine: Merge the two sorted subsequences to produce the sorted sequence.
Variations
- top-down
- usually recursive
- stop repetition when the size of section is 1 or 0
- bottom-up (iterative, not mentioned in the book)
  - usually iterative
  - merge all n size 1 sections (single element) into n/2 size 2 sections
  - merge all size 2 lists to n/4 size 4 lists
  - continue until done

Complexity

Time
- $\Theta(n \log n)$ best/worst/average case
Space
- $\Theta(n)$ for new array
- $\Theta(\log n)$ for recursion stack
- Unoptimized recursive $\Theta(n \log n)$
- Optimized recursive $\Theta(n)$
- Iterative $\Theta(n)$

Visualization Website

Our lab steps through top-down merge sort and shows how equal cards retain or change their relative order. The other visualizations below provide additional views.