On the Average Case of MergeInsertion

Florian Stober, Armin Weiß

MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of compa…