Sorting Algorithms

Insertion Sort

builds a sorted left portion by inserting each element into its correct position

Insertion Sort Runtime Best

O(n)

Insertion Sort Runtime Average

O(n^2)

Insertion Sort Runtime Worst

O(n^2)

Insertion Sort Stable

yes

Insertion Sort In-Place

yes

Selection Sort

repeatedly finds the minimum and swaps it into place

Selection Sort Runtime Best

O(n^2)

Selection Sort Runtime Average

O(n^2)

Selection Sort Runtime Worst

O(n^2)

Selection Sort Stable

no

Selection Sort In-Place

yes

Merge Sort

divide array into halves recursively then merge sorted halves

Merge Sort Runtime Best

O(n log n)

Merge Sort Runtime Average

O(n log n)

Merge Sort Runtime Worst

O(n log n)

Merge Sort Stable

yes

Merge Sort In-Place

no

Heap Sort

builds a heap and repeatedly extracts min/max and rebuilds heap

Heap Sort Runtime Best

O(n log n)

Heap Sort Runtime Average

O(n log n)

Heap Sort Runtime Worst

O(n log n)

Heap Sort Stable

no

Heap Sort In-Place

yes

Quick Sort

choose a pivot and partition into < pivot and > pivot recursively

Quick Sort Runtime Best

O(n log n)

Quick Sort Runtime Average

O(n log n)

Quick Sort Runtime Worst

O(n^2)

Quick Sort Stable

no

Quick Sort In-Place

yes

Bucket Sort

distributes elements into buckets

Bucket Sort Runtime Best

O(n + k)

Bucket Sort Runtime Average

O(n + k)

Bucket Sort Runtime Worst

O(n^2)

Bucket Sort Stable

yes (if bucket sort uses stable sub-sort)

Bucket Sort In-Place

no

Radix Sort Runtime Best

O(d(n + k))

Radix Sort Runtime Average

O(d(n + k))

Radix Sort Runtime Worst

O(d(n + k))

Radix Sort Stable

yes

Radix Sort In-Place

no

Radix Sort

sorts digits from least to most significant using stable counting sort