Java Reference
In-Depth Information
36
20
17
13
28
14
23
15
20
36
13
17
14
28
15 23
13
17
20
36
14
15
23
28
13
14
15
17
20
23
28 36
Figure7.8
An illustration of Mergesort. The first row shows eight numbers that
are to be sorted. Mergesort will recursively subdivide the list into sublists of one
element each, then recombine the sublists. The second row shows the four sublists
of size 2 created by the first merging pass. The third row shows the two sublists
of size 4 created by the next merging pass on the sublists of row 2. The last row
shows the final sorted list created by merging the two sublists of row 3.
Mergesort is one of the simplest sorting algorithms conceptually, and has good
performance both in the asymptotic sense and in empirical running time. Surpris-
ingly, even though it is based on a simple concept, it is relatively difficult to im-
plement in practice.
Figure 7.8 illustrates Mergesort.
A pseudocode sketch of
Mergesort is as follows:
Listmergesort(Listinlist){
if(inlist.length()<=1)returninlist;;
ListL1=halfoftheitemsfrominlist;
ListL2=otherhalfoftheitemsfrominlist;
returnmerge(mergesort(L1),mergesort(L2));
}
Before discussing how to implement Mergesort, we will first examine the merge
function. Merging two sorted sublists is quite simple. Function
merge
examines
the first element of each sublist and picks the smaller value as the smallest element
overall. This smaller value is removed from its sublist and placed into the output
list. Merging continues in this way, comparing the front elements of the sublists and
continually appending the smaller to the output list until no more input elements
remain.
Implementing Mergesort presents a number of technical difficulties. The first
decision is how to represent the lists. Mergesort lends itself well to sorting a singly
linked list because merging does not require random access to the list elements.
Thus, Mergesort is the method of choice when the input is in the form of a linked
list. Implementing
merge
for linked lists is straightforward, because we need only
remove items from the front of the input lists and append items to the output list.
Breaking the input list into two equal halves presents some difficulty. Ideally we
would just break the lists into front and back halves. However, even if we know the
length of the list in advance, it would still be necessary to traverse halfway down
the linked list to reach the beginning of the second half. A simpler method, which
does not rely on knowing the length of the list in advance, assigns elements of the
