# 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 $2m-1$.

Given different sized partitions $m\le l$ the worst case comparisons is $m+l-1$. 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\left(n\right)=\left\{\begin{array}{cc}0& ifn=0\\ 2T\left(\frac{n}{2}\right)+\left(n-1\right)& \text{otherwise}\end{array}$

The closed-form is $T\left(n\right)=nlgn-n+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.

• The $\frac{n}{2}$ leaves do $0$ comparisons.
• The $\frac{n}{4}$ parents do $2$ comparisons.
• The $\frac{n}{8}$ grandparents do $4$ comparisons.
• $\dots$

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

• $0\left(\frac{n}{2}\right)+2\left(\frac{n}{4}\right)+4\left(\frac{n}{8}\right)+\dots$
• $=\left(\frac{n}{2}\right)\left(\frac{1}{1}+\frac{2}{2}+\frac{3}{4}+\frac{4}{8}+\dots \right)$
• $=\left(\frac{n}{2}\right)\left($
• $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots =2$
• $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots =1$
• $\frac{1}{4}+\frac{1}{8}+\dots =\frac{1}{2}$
• $\frac{1}{8}+\dots =\frac{1}{4}$
• $\dots \right)=\left(\frac{n}{2}\right)\left(4\right)$
• $=2n$

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.

• $\underset{i=0}{\overset{n-1}{\Sigma }}2lg\left(n-1\right)$
• $=2nlgn+O\left(n\right)$

## 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.

• $T\left(n\right)=\left(n-1\right)+T\left(n-1\right)$
• $=\underset{i=1}{\overset{n-1}{\Sigma }}i$
• $=\frac{\left(n-1\right)n}{2}$

For the best case, partitions are equally sized.

• $T\left(n\right)=2T\left(\frac{n-1}{2}\right)+\left(n-1\right)$
• $\le 2T\left(\frac{n}{2}\right)+\left(n-1\right)$
• $\approx nlgn-n+1$ (constructive induction)

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

• $T\left(n\right)=T\left(3\frac{n}{4}\right)+T\left(\frac{n}{4}\right)+\left(n-1\right)$
• $\approx 1.23nlgn$

The exact reccurence is:

$T\left(n\right)=\left\{\begin{array}{cc}0& ifn=1\\ \left(n-1\right)+\underset{q=1}{\overset{n}{\Sigma }}\left(\frac{1}{n}\right)\left(T\left(q-1\right)+T\left(n-q\right)\right)& \text{otherwise}\end{array}$

The closed form solution (through constructive induction) is: $\approx 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. Consider choice of pivot $k$:

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

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

• $\underset{1\le i\le j\le n}{\Sigma }\frac{2}{j-i+1}$
• $=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=i+1}{\overset{n}{\Sigma }}\frac{2}{j-i+1}$
• $=2\left(n+1\right){H}_{n}+4n$