Merge sort

Merge sort is a comparison-based sorting algorithm that recursively divides a sequence, sorts the smaller parts, and merges them into order. Its worst-case running time is O(n log n).

Divide-and-conquer algorithm: An algorithmic strategy that splits a problem into smaller subproblems, solves them, and combines their results. Merge sort applies this strategy by splitting sequences and combining sorted results.
Sorting algorithm: An algorithm that rearranges items according to an ordering criterion. Merge sort is one method for arranging items into a specified order.
Quicksort: A comparison sort that partitions items around a pivot and recursively sorts the resulting partitions. Quicksort often sorts arrays in place, while merge sort offers a worst-case O(n log n) bound.
External sorting: Sorting methods designed for data that exceeds available main memory and resides in external storage. External merge sort processes disk-sized data through sorted runs and repeated merges.
John von Neumann: A mathematician and computer scientist whose work helped establish modern computing and numerical analysis. He is credited with developing merge sort in 1945 for the EDVAC project.
Merge operation: A procedure that combines two sorted sequences into one sorted sequence. This step restores global order after merge sort recursively sorts both halves.
Comparison sort: A sorting algorithm whose decisions depend on comparisons between keys. Merge sort learns the order of items through comparisons rather than key-specific operations.
Heapsort: A comparison sort that builds a heap and repeatedly removes its largest or smallest element. Heapsort has O(n log n) worst-case time with constant auxiliary array space, unlike typical merge sort.
K-way merge: The process of combining k sorted sequences into one sorted sequence. External sorting generalizes pairwise merging to combine many runs efficiently.
EDVAC: An early stored-program electronic computer designed in the United States after World War II. Merge sort’s early account was connected to plans for sorting data on this machine.

Linked from 12 pages