Sorting Basics

1Introduction

This lecture defines the specification and evaluation criteria of sorting and explains the correctness and complexity of insertion sort and merge sort. A sorted array is a prerequisite for the subsequent binary-search lecture.

2Sorting specification

Let $$A=(a_0,\dots ,a_{n-1})$$A=(a_0,\ldots,a_{n-1}) be a sequence, and let a key function $$k$$k map each element to a totally ordered set. An ascending sorting algorithm produces $$B=(b_0,\dots ,b_{n-1})$$B=(b_0,\ldots,b_{n-1}) satisfying both conditions below.

1. $$B$$B is a permutation of $$A$$A; the multiplicity of every element is preserved.
2. $$k\left(b_0\right)\le k\left(b_1\right)\le \cdots \le k\left(b_{n-1}\right)$$k(b_0)\leq k(b_1)\leq\cdots\leq k(b_{n-1}).

The first condition prohibits lost or duplicated elements, and the second specifies the output order.

3Evaluation criteria

3.1Stability

A stable sort preserves the relative output order of any two elements satisfying $$i<j$$i<j and $$k\left(a_i\right)=k\left(a_j\right)$$k(a_i)=k(a_j). This property preserves the result of an earlier sort when sorting by several keys in stages.

3.2In-place operation

An in-place sort updates the input array using $$O\left(1\right)$$O(1) auxiliary space rather than an additional array proportional to $$n$$n. An analysis must state whether it includes recursive call-stack space.

3.3Comparison model

A comparison sort obtains information about keys only through results such as $$k\left(x\right)\le k\left(y\right)$$k(x)\leq k(y). Below, each comparison and assignment takes $$O\left(1\right)$$O(1) time, and complexity denotes worst-case time unless stated otherwise.

4Insertion sort

Insertion sort takes $$a_i$$a_i for $$i=1,2,\dots ,n-1$$i=1,2,\ldots,n-1 and inserts it into its proper position in the sorted prefix $$A[0,i)$$A[0,i). It shifts right only elements whose keys are greater than the inserted key.

4.1Correctness

Use the following loop invariant: at the start of iteration $$i$$i, $$A[0,i)$$A[0,i) contains exactly the original elements of that prefix in nondecreasing order.

• For $$i=1$$i=1, a one-element prefix is sorted.
• Shifting elements greater than $$a_i$$a_i and inserting $$a_i$$a_i immediately before them preserves all elements and makes $$A[0,i+1)$$A[0,i+1) sorted.
• At $$i=n$$i=n, the prefix is the entire array.

Thus insertion sort satisfies the sorting specification. It is stable because equal-key elements do not pass each other, and it is in-place because it requires only a temporary variable.

4.2Complexity

For an already sorted input, every iteration performs a constant number of comparisons, so the time complexity is $$\mathrm{\Theta }\left(n\right)$$\Theta(n). In reverse order, insertion $$i$$i requires $$i$$i shifts, giving $$\sum _{i=1}^{n-1}i=\mathrm{\Theta }\left(n^2\right)$$\sum_{i=1}^{n-1}i=\Theta(n^2) total work.

5Merge sort

Merge sort divides a sequence until every part has length at most $$1$$1, recursively sorts the parts, and merges two sorted sequences. A merge compares their first remaining elements and transfers the smaller one to the output.

5.1Correctness

For merging, maintain the invariant that the produced sequence is sorted and contains exactly the elements removed from the two inputs. The smaller of the two first remaining elements is a minimum among all remaining elements, so appending it preserves the invariant. At termination, every element has been produced.

Induction on sequence length now proves the whole algorithm correct. Sequences of length $$0$$0 or $$1$$1 are trivially sorted. The inductive hypothesis gives two correctly sorted shorter sequences, and the correct merge produces a sorted permutation of the original sequence.

If equal keys are resolved by taking the left element first, merge sort is stable. A standard array implementation uses $$O\left(n\right)$$O(n) auxiliary merge storage and is therefore not in-place.

5.2Complexity

Merging a total of $$n$$n elements takes $$\mathrm{\Theta }\left(n\right)$$\Theta(n) time. The time complexity $$T\left(n\right)$$T(n) satisfies

The recursion tree has height $$\lceil {\log }_{2}n\rceil$$\lceil\log_2 n\rceil, and the subproblem lengths at any one depth sum to $$n$$n. Hence the merge cost at each depth is at most $$O\left(n\right)$$O(n), giving an $$O\left(n\log n\right)$$O(n\log n) upper bound. At every depth $$0\le d<\lfloor {\log }_{2}n\rfloor$$0\leq d<\lfloor\log_2 n\rfloor, subproblems of length at least $$2$$2 have total length $$\mathrm{\Theta }\left(n\right)$$\Theta(n), giving an $$\mathrm{\Omega }\left(n\log n\right)$$\Omega(n\log n) lower bound. Therefore, $$T\left(n\right)=\mathrm{\Theta }\left(n\log n\right)$$T(n)=\Theta(n\log n).

In a standard array implementation, a reusable merge array uses $$\mathrm{\Theta }\left(n\right)$$\Theta(n) space and the call stack uses $$\mathrm{\Theta }\left(\log \right(n+1\left)\right)$$\Theta(\log(n+1)) space. Thus, the total auxiliary-space complexity, including the call stack, is $$\mathrm{\Theta }\left(n\right)$$\Theta(n). An empty sequence terminates immediately.

6Lower bound for comparison sorting

There are $$n!$$n! input orders of $$n$$n elements with mutually distinct keys. The binary decision tree of a deterministic comparison sort needs at least $$n!$$n! leaves to distinguish these orders, so its height is at least $$\lceil {\log }_2(n!)\rceil$$\lceil\log_2(n!)\rceil. For $$n\ge 2$$n\geq2, the inequality $$n!\ge (n/2{)}^{n/2}$$n!\geq(n/2)^{n/2} implies $${\log }_2(n!)=\mathrm{\Omega }\left(n\log n\right)$$\log_2(n!)=\Omega(n\log n). Hence every deterministic comparison sort requires $$\mathrm{\Omega }\left(n\log n\right)$$\Omega(n\log n) comparisons in the worst case. Merge sort's $$\mathrm{\Theta }\left(n\log n\right)$$\Theta(n\log n) bound is asymptotically optimal in this model.

7Connection to binary search

Binary search assumes $$A_0\le A_1\le \cdots \le A_{n-1}$$A_0\leq A_1\leq\cdots\leq A_{n-1}. For a single query on unsorted input, the cost of sorting may exceed its benefit. For repeated queries on the same array, sorting once in $$O\left(n\log n\right)$$O(n\log n) time and then performing each query in $$O\left(\log n\right)$$O(\log n) time can be effective.