Merge-insertion sort

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, merge-insertion sort or the Ford–Johnson algorithm is a <a href="/facts/Comparison_sort/X1PvE50c">comparison sorting</a> algorithm published in 1959 by <a href="/facts/L._R._Ford_Jr./G4LQAG4W">L. R. Ford Jr.</a> and <a href="/facts/Selmer_M._Johnson/b565hMED">Selmer M. Johnson</a>. It uses fewer comparisons in the <a href="/facts/Worst_case_analysis/9ERhKtxB">worst case</a> than the best previously known algorithms, <a href="/facts/Insertion_sort/N5yWe8Co">binary insertion sort</a> and <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a>, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by <a href="/facts/Stanis%C5%82aw_Trybu%C5%82a/IymAzcI1">Stanisław Trybuła</a> and Czen Ping.
</p>

Merge-insertion sort open-in-new

Merge-insertion sort