Write the complete algorithm for the merge insert sort sketched out in Section 15.7.

Data From Section 15.7:

We will use binary insert to place the losers. However, we are free to choose the best ordering for inserting, keeping in mind the fact that binary search is best for 2ⁱ − 1 items. So we pick the order of inserts to optimize the binary searches. This sort is called merge insert sort, and also known as the Ford and Johnson sort. For ten elements, given the poset shown in Figure 15.6 we fold in the last four elements (labeled 1 to 4) in the order Element 2, Element 1, Element 3, and finally Element 4.

Figure 15.6: