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


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

1 Answer 1


This is just Bubble-Sort in disguise. Each time, you get the biggest element pushed to the end of the array, then you sort the remaining of the array.

Your recurrence is correct.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.