Although the general strategy uses MERGE to put the pieces back together, there is a specific version of the general strategy called Merge Sort. The defining feature of Merge Sort is that in step (1), the given list is divided into two equal size pieces (or as near equal as possible).
There are various ways of dividing L into 2 equal pieces, we will illustrate the algorithm by putting the first half of L in one piece and the second half of L in the other piece. We proceed until we're down to singleton or empty lists, which are always sorted, then we work our way back up the recursion by MERGING together the short lists into larger ones (which replace the list that we started with at that level).
The slowest step in this algorithm is the MERGE operation. Earlier we looked at two special cases of MERGE - INSERT and JOIN. How can we change the way we do step (1) - SPLIT L into pieces - so that we can use INSERT or JOIN instead of MERGE?
