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.
method statements average time worst-case time
insertion sort 9 O (n 2) O (n 2)
shell sort 17 O (n 1.25) O (n 1.5)
quicksort 21 O (n lg n ) O (n 2)
Table 2-2: Comparison of Methods
count insertion shell quicksort
16 39 ms 45 ms 51 ms
256 4,969 ms 1,230 ms 911 ms
4,096 1.315 sec .033 sec .020 sec
65,536 416.437 sec 1.254 sec .461 sec