Mergesort

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

All available visualizations are for top-down merge sort.