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^7/6) O(n^4/3)

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^7/6)	O(n^4/3)
quicksort	21	O(n lg n)	O(n²)

Table 2-3: Sort Timings
count insertion shell quicksort

16 39 盜 45 盜 51 盜

256 4 969 盜 1 230 盜 911 盜

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 盜	45 盜	51 盜
256	4 969 盜	1 230 盜	911 盜
4 096	1.315 sec	.033 sec	.020 sec
65 536	416.437 sec	1.254 sec	.461 sec