# 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*^{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-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 |