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] &gt; 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] &gt; 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
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$$.