Java Reference
In-Depth Information
FIGURE 9-4
A worst-case merge of two sorted arrays
First array
Second array
2
6
4
8
a. 2 < 4, so copy 2 to new array
b. 6 > 4, so copy 4 to new array
b
a
c
d
c. 6 < 8, so copy 6 to new array
d. Copy 8 to new array
8
4 6
New merged array
2
If
n
is 2
k
, the
k
levels of recursive calls to
mergeSort
result in
k
levels of merges. The merges at
each level are O(
n
). Since
k
is log
2
n
,
mergeSort
is O(
n
log
n
). When
n
is not a power of 2, we can
find an integer
k
so that 2
k
- 1
<
n
<
2
k
. For example, when
n
is 15,
k
is 4. Thus,
k
-
1
<
log
2
n
<
k
so if we round log
2
n
up, we will get
k
. Therefore, the merge sort is O(
n
log
n
) in this case as well.
Notice that the merge steps are O(
n
) regardless of the initial order of the array. Merge sort is then
O(
n
log
n
) in the worst, best, and average cases.
A disadvantage of merge sort is the need for the temporary array during the merge step. At the
beginning of Chapter 8, we spoke of sorting the topics on your bookshelf by height. We were able
to do so without the extra space that another shelf or the floor would provide. You can see now that
the merge sort would require this extra space. Later in this chapter, you will see another algorithm
that sorts in O(
n
log
n
) time without a second array.
Note:
The time efficiency of merge sort
Merge sort is O(
n
log
n
) in all cases. Its need for a temporary array is a disadvantage. The
time required for copying entries, however, is less in Java than in other programming lan-
guages, since references are copied instead of the actual objects.
9.7
Assessing efficiency another way.
In Chapter 7, we used a recurrence relation to estimate the time
efficiency of recursive algorithms. We can use the same technique here. If
t
(
n
) represents the time
requirement of
mergeSort
in the worst case, the two recursive calls each require time
t
(
n
/
2). The
merge step is O(
n
). Thus, we have the following:
t
(
n
)
=
t
(
n
/
2)
+
t
(
n
/
2)
+
n
=
2
t
(
n
/
2)
+
n
when
n
>
1
t
(1)
=
0
As a first step in solving this recurrence relation, we evaluate it for a specific value of
n
. Since
t
(
n
) involves
n
/
2, choosing
n
to be a power of 2—8, for example—is convenient. We then have
t
(8)
=
2
t
(4)
+
8
t
(4)
=
2
t
(2)
+
4
t
(2)
=
2
t
(1)
+
2
=
2
By substituting repeatedly, we get the following for
t
(8):
t
(8)
=
2
t
(4)
+
8
=
2 [2
t
(2)
+
4]
+
8
=
4
t
(2)
+
8
+
8
