Logarithmic Sorts

Merge sort

Algorithm.

proc merge-sort(A, p, r)
	if p < r then
		q = floor((p + r)/2)
		merge-sort(A, p, q)
		merge-sort(A, q+1, r)
		merge(A, (p,q), (q+1,r))

Complexity (merge comparisons). Assuming we have equal partitions with length m, the best is (consecutive partitions) is m and the worst (interleaved partitions) is 2m1.

Given different sized partitions ml the worst case comparisons is m+l1. When m is significantly less than l you can use binary search to improve performance.

Complexity (merge sort comparisons). We will only analyze the worst case. The recurrence is:

T(n)={0ifn=02T(n2)+(n1)otherwise

The closed-form is T(n)=nlgnn+1.

Heap sort

Algorithm.

proc heap-sort(A, n)
	for r = floor(n/2) downto 1 do sift(r, n)
	for m = n downto 2 do
		A[1] <-> A[m]
		sift(1, m-1)
proc sift(p, m)
	c = 2*p
	while c <= m
		if c < m then
			if A[c+1] > A[c] then
				c = c + 1
		if A[c] > A[p] then
			A[p] <-> A[c]
			p = c
			c = 2*p
		else
			exit

Complexity (creation comparisons). We consider the worst case for creating the heap.

We can find a closed form of this sum with some clever algebra.

Complexity (heap sort comparisons). We consider the worst case for heap sort. We require two comparisons for every mini-heap. Sifts are proportional to the levels below the current node.

Quick sort

Algorithm.

proc quick-sort(A, p, r)
	if p < r then
		q = partition(A, p, r)
		quick-sort(A, p, q-1)
		quick-sort(A, q+1, r)
func partition(A, p, r)
	x = A[r]
	i = p-1
	for j = p to r-1 do
		if A[j] < r then
			i = i + 1
			A[i] <-> A[j]
	A[i+1] <-> A[r]
	return i+1

Complexity (comparisons).

For the worst case, the list is already sorted.

For the best case, partitions are equally sized.

For the average case, we can approximate with a reccurence:

The exact reccurence is:

T(n)={0ifn=1(n1)+Σq=1n(1n)(T(q1)+T(nq))otherwise

The closed form solution (through constructive induction) is: 1.39nlgn.

Another more clever argument can be used to get the exact answer without the difficult reccurence. Consider elements i and j such that i<j. Consider choice of pivot k:

  1. If k<i this has no effect.
  2. If k=i the elements are compared.
  3. If i<k<j the elements aren’t compared.
  4. If k=j the elements are compared.
  5. If j<k this has no effect.

We just sum the probability that each pair is compared to one another: