SORTING - Introduction to Java Programming: Comprehensive Version - page 870

Let T(n) denote the time required for sorting an array of n elements using a merge sort. With-
out loss of generality, assume n is a power of 2. The merge sort algorithm splits the array into
two subarrays, sorts the subarrays using the same algorithm recursively, and then merges the
subarrays. Therefore,

merge sort time complexity

n
2

n
2

T ( n ) = T ¢ ≤ + T ¢ ≤ + mergetime

n
2

n
2

The first T ¢ ≤ is the time for sorting the first half of the array, and the second T ¢ ≤ is the

time for sorting the second half. To merge two subarrays, it takes at most n 1 comparisons

to compare the elements from the two subarrays and n moves to move elements to the tempo-
rary array. Thus, the total time is 2 n

-

- 1. Therefore,

n
2

n
2

T ( n ) = T ¢ ≤ + T ¢ ≤ + 2 n - 1 = O ( n log n )

The complexity of a merge sort is O ( n log n ). This algorithm is better than selection sort, insertion
sort, and bubble sort, because the time complexity of these algorithms is O ( n 2 ). The sort method
in the java.util.Arrays class is implemented using a variation of the merge sort algorithm.

O ( n log n ) merge sort

23.7

✓ ✓

Describe how a merge sort works. What is the time complexity for a merge sort?

Check

23.8

Point

Use Figure 23.4 as an example to show how to apply a merge sort on {45, 11, 50, 59,
60, 2, 4, 7, 10}.

23.9

What is wrong if lines 6-15 in Listing 23.6, MergeSort.java, are replaced by the fol-
lowing code?

// Merge sort the first half
int [] firstHalf = new int [list. length / 2 + 1 ];
System.arraycopy(list, 0 , firstHalf, 0 , list. length / 2 + 1 );
mergeSort(firstHalf);

// Merge sort the second half
int secondHalfLength = list. length - list. length / 2 - 1 ;
int [] secondHalf = new int [secondHalfLength];
System.arraycopy(list, list. length / 2 + 1 ,
secondHalf, 0 , secondHalfLength);
mergeSort(secondHalf);

23.5 Quick Sort
A quick sort works as follows: The algorithm selects an element, called the pivot, in
the array. It divides the array into two parts, so that all the elements in the first part
are less than or equal to the pivot and all the elements in the second part are greater
than the pivot. The quick sort algorithm is then recursively applied to the first part and
then the second part.

Key
Point

quick sort

The quick sort algorithm, developed by C.A.R. Hoare in 1962, is described in Listing 23.7.

L ISTING 23.7

Quick Sort Algorithm
1 public static void quickSort( int [] list) {
2 if (list.length > 1 ) {
3 select a pivot;
4 partition list into list1 and list2 such that

base condition
select the pivot
partition the list