# Run-time of Sorting Algorithm

Problem

Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $$A$$ of $$n$$ integers with no duplicates.

sort(A, i, j)
if i = j
return
m = floor[(i + j)/2]
sort(A, i, m)
sort(A, m + 1, j)
if A[m] > A[j]
swap A[m] and A[j]
sort(A, i, j - 1)


Write a recurrence that characterizes the runtime of sort(A, 0, n-1).

Attempted Solution

Let $$T(n)$$ be the run-time of sort(A, 0, n-1)

if i = j then return $$\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$$

m = floor[(i + j)/2] $$\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$$

sort(A, i, m) $$\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$$

sort(A, m + 1, j) $$\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$$

if A[m] > A[j] then swap A[m] and A[j] $$\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$$

sort(A, i, j - 1) $$\hspace{0.1cm} = \hspace{0.1cm} T(n - 1)$$

$$\therefore T(n) \hspace{0.1cm} = \hspace{0.1cm} 2 \hspace{0.1cm} T(\frac{n}{2}) \hspace{0.1cm} + \hspace{0.1cm} T(n - 1) + \hspace{0.1cm} O\hspace{0.01cm}(1)$$

Is this correct? Feedback would be greatly appreciated.

Sort in Action

The sort algorithm actually works. See this example to convince yourself.

https://imgur.com/G5FUewE

• does this really sorts? – kelalaka Oct 9 '18 at 8:57
• Yes it does. But that is besides the point here, I need a recurrence. – turing Oct 9 '18 at 9:02
• Yes, your argument is correct. – kelalaka Oct 9 '18 at 9:05
• Wonderful, thank you. I posted a pic where I compiled this algorithm with a test case - it actually sorted! – turing Oct 9 '18 at 9:06
• Yes, I looked again and saw that, apart from exercise, no use. – kelalaka Oct 9 '18 at 9:07

An upper bound would be $$T(n) = O(2^n)$$.
Proof: For large enough $$n$$, we have $$T(n)\leq 2^n$$. This is the base case for induction. Induction hypothesis is $$T(n)\leq 2^n$$. So, we have $$2\sqrt{2^n}+\frac{2^n}2+O(1)\leq 2^n$$.