Wing

Sorting Algorithms

1940s

Merge Sort

John von Neumann, 1945

A divide-and-conquer algorithm that recursively splits an array in half, sorts each half, and merges the sorted halves back together.

1950s

Radix Sort

Harold Seward, 1954

Non-comparative sort that distributes elements into buckets by individual digits, processing from least significant to most significant.

Counting Sort

Herman H. Seward, 1954

Counts occurrences of each key, then fills the output by walking buckets in order (integer keys).

Bubble Sort

Folklore, 1956

Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Quick Sort

Tony Hoare, 1959

Selects a pivot element and partitions the array so that smaller elements go left and larger go right, then recurses on each side.

Shell Sort

Donald Shell, 1959

An optimization of insertion sort that compares elements separated by a gap, progressively reducing the gap to 1.

Insertion Sort

Various, 1959

Builds a sorted prefix by shifting each new element left until it lands among smaller neighbors.

1960s

Selection Sort

Various, 1963

Each pass scans the unsorted suffix for the minimum and swaps it to the front.

Heap Sort

J.W.J. Williams, 1964

Builds a max-heap from the array, then repeatedly extracts the maximum element to produce a sorted sequence.

1990s

Tim Sort

Tim Peters, 1993

A hybrid sorting algorithm that identifies natural runs in the data, then merges them efficiently using techniques from merge sort and insertion sort.