Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 803

1000
2000
4000
8000
16000
32000
64000
128000
256000

N Runtime (ms)

0
16
47
234
657
2562
10265
41141
164985

200000
150000
100000
50000
0

Input size (N)

Figure 13.6 Runtimes for selection sort algorithm

1)/2, which is just over 1 ⁄ 2 N 2 . Figure
13.6 supports this analysis, because the runtime quadruples every time the input size
N is doubled, which is characteristic of an N 2 algorithm. The algorithm becomes
impractically slow once the number of elements reaches tens of thousands.
The current selectionSort code will sort arrays of integer values, but you could
adapt it to sort Comparable objects such as String s using the techniques covered in the
previous section on searching objects. For example, you could use the compareTo and
equals methods to compare objects rather than relational operators like < and >= .

from 1 to any maximum value N equals ( N )( N

13.4 Case Study: Implementing Merge Sort

There are other algorithms similar to selection sort that make many passes over the
array and swap various elements on each pass. An algorithm that searches for
inverted pairs of elements and swaps them into order in this way cannot run faster
than O( N 2 ), on average. However, there is a better algorithm that breaks this barrier.
The merge sort algorithm is named for the observation that if you have two sorted
subarrays, you can easily merge them into a single sorted array. For example, con-
sider the following array:

int[] list = {14, 32, 67, 76, 23, 41, 58, 85};

You can think of it as two subarray halves, each of which (because of the element
values we chose) happens to be sorted:

0 12345

58 85

67

14 32 67 76 23 41

subarray subarray