Comparison

In this section we will compare the sorting algorithms covered: insertion sort, shell sort, and quicksort. There are several factors that influence the choice of a sorting algorithm:

Stable sort. Recall that a stable sort will leave identical keys in the same relative position in the sorted output. Insertion sort is the only algorithm covered that is stable.
Space. An in-place sort does not require any extra space to accomplish its task. Both insertion sort and shell sort are in- place sorts. Quicksort requires stack space for recursion, and therefore is not an in-place sort. Tinkering with the algorithm considerably reduced the amount of time required.
Time. The time required to sort a dataset can easily become astronomical (Table 1-1). Table 2-2 shows the relative timings for each method. The time required to sort a randomly ordered dataset is shown in Table 2-3.
Simplicity. The number of statements required for each algorithm may be found in Table 2-2. Simpler algorithms result in fewer programming errors.

Table 2-2: Comparison of Sorting Methods

method statements average time worst-case time

insertion sort 9 O(n²) O(n²)

shell sort 17 O(n^1.25) O(n^1.5)

quicksort 21 O(n lg n) O(n²)

Table 2-2: Comparison of Sorting Methods
method	statements	average time	worst-case time
insertion sort	9	O(n²)	O(n²)
shell sort	17	O(n^1.25)	O(n^1.5)
quicksort	21	O(n lg n)	O(n²)

Table 2-3: Sort Timings

count insertion shell quicksort

16 39 µs 45 µs 51 µs

256 4,969 µs 1,230 µs 911 µs

4,096 1.315 sec .033 sec .020 sec

65,536 416.437 sec 1.254 sec .461 sec

count	insertion	shell	quicksort
16	39 µs	45 µs	51 µs
256	4,969 µs	1,230 µs	911 µs
4,096	1.315 sec	.033 sec	.020 sec
65,536	416.437 sec	1.254 sec	.461 sec