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.