9: Sorting Algorithms

Unit Introduction

A sorting algorithm is an algorithm that puts elements of a collection such as array or list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms, such as in search and merge algorithms that require sorted collections to work correctly. It is also often useful for normalization of data and for producing human-readable output. More precisely, the output must satisfy two conditions (i) the output is in non-decreasing order (each element is no smaller than the previous element according to the desired total order) and (ii) the output is a permutation, or reordering, of the input.

The Sorting algorithms used in computer science are often classified by:

1. Computational complexity (worst, average and best case behavior) in terms of the size of the list (n) - For typical sorting algorithms good behavior is O(n log n) and bad behavior is O(n2). Ideal behavior for a sort is O(n). Sort algorithms which only use an abstract key comparison operation often require at least O(n log n) comparisons on average.

2. Memory usage (and use of other computer resources) - In particular, some sorting algorithms are “in place”, such that little memory is needed beyond the items being sorted, while others need to create auxiliary locations for data to be temporarily stored.

3. Stability - Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

4. Whether or not is a comparison sort - A comparison sort examines the data only by comparing two elements with a comparison operator.

5. General sort method – whether uses insertion, exchange, selection, merging, etc.

Table \(\PageIndex{1}\) provides a summary of some sorting algorithms and their classification. When equal elements are indistinguishable, such as with integers, stability is not an issue. However, assume that the following pairs of numbers are to be sorted by their first coordinate: (4, 1) (3, 1) (3, 7) (5, 6). In this case, two different results are possible, that is, one which maintains the relative order of records with equal keys, and one which does not as shown below:

(3, 1) (3, 7) (4, 1) (5, 6) (order maintained)

(3, 7) (3, 1) (4, 1) (5, 6) (order changed)

Unstable sorting algorithms may change the relative order of records with equal keys, but stable sorting algorithms never do so. Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker. Remembering this order, however, often involves an additional space cost.

Table \(\PageIndex{1}\), presents a classification summary of the sorting algorithms considered in this unit. In the table, n is the number of records to be sorted. The columns “Best”, “Average”, and “Worst” give the time complexity in each case. “Memory” denotes the amount of auxiliary storage needed beyond that used by the collection list itself. “Cmp” indicates whether the sort is a comparison sort.

Table \(\PageIndex{1}\): A Sorting Algorithms Classification

Key Terms

Sorting: A process that puts elements of a collection such as array or list in a certain order

Learning Activities