Merge-Insertion Sort

Merge-insertion sort, or the Ford-Johnson algorithm, is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson, using fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort. For twenty years it was the sorting algorithm known to use the fewest comparisons, and although it is not of practical significance today, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons; the same algorithm may also have been discovered independently by Stanislaw Trybula and Czen Ping.