Merge sort

lastmod 2025-03-14created 2025-03-141 edits

Merge sort is an O(n log n) comparison-based sorting algorithm. When implemented in the usual way, it is a stable sort, and it is a divide and conquer algorithm. It was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Herman Goldstine and von Neumann in early 1948.