84 SORTING ALGORITHMS
last the index of the last element in the part of list to sort
if first < last then
middle = ( first + last ) / 2
MergeSort( list, first, middle )
MergeSort( list, middle + 1, last )
MergeLists( list, first, middle, middle + 1, last )
end if
It should be obvious that the work is all being done in the function Merge-
Lists. We now will develop MergeLists.
Consider lists A and B, both sorted in increasing order. This ordering means
that the smallest element of each list is in the first location, and the largest ele-
ment of each list is in the last location. To merge these together into one list,
we know that the smallest element overall must be either the first element of A
or the first element of B, and the largest element overall must be either the last
element of A or the last element of B. If we want to create a new list C that is
the sorted combination of A and B, we will begin by moving the smaller of
A[1] and B[1] into C[1]. But what gets moved into C[2]? If A[1] was smaller
than B[1], A[1] was moved into C[1], and the next element might be B[1]
unless A[2] is also smaller than B[1]. This is possible because all we really know
is that A[2] is larger than A[1] and smaller than A[3], but we don’t know how
the elements of A relate in size to the elements of B. It seems that the best way
to accomplish the merge would be to have two indices for A and B and incre-
ment the index for the list that has the smaller element. The general process
keeps comparing the smallest elements of what is left of lists A and B and
moves the smaller of these two into C. At some point, however, we will “run
out” of elements in either list A or B. The elements “left over” will be those in
one list that are greater than the last element of the other list. We need to make
sure that these elements are moved to the end of the result list.
Putting these ideas together into an algorithm gives us
MergeLists( list, start1, end1, start2, end2 )
list the elements to be put into order
start1 beginning of “list” A
end1 end of “list” A
start2 beginning of “list” B
end2 end of “list” B
// assumes that the elements of A and B are contiguous in list
finalStart = start1