慢排序的时间复杂度

Question

最近对各种排序算法的时间复杂度以及如何计算很感兴趣。然而，尽管我尽了最大努力，但我一直无法找到合适的 Big O 表示的慢排序算法，如下所示，用 Python 实现：

def _slowsort(a, i, j):
    """in-place sorts the integers in the array
    spanning indexes [i, j].
    """
    # base condition; then no need of sorting if
    #  - there is one element to sort
    #  - when start and end of the array flipped positions
    if i >= j:
        return

    # find the mid index of the array so that the
    # problem could be divided intto sub-problems of
    # smaller spans
    m = (i + j) // 2

    # invoke the slowsort on both the subarrays
    _slowsort(a, i, m)
    _slowsort(a, m + 1, j)

    # once both the subproblems are solved, check if
    # last elements of both subarrays and move the
    # higher among the both to end of the right subarray
    # ensuring that the highest element is placed at the
    # correct relative position
    if a[m] > a[j]:
        a[m], a[j] = a[j], a[m]

    # now that the rightmost element of the array is at
    # the relatively correct position, we invoke Slowsort on all
    # the elements except the last one.
    _slowsort(a, i, j - 1)


def slowsort(a):
    """in-place sorts the array `a` using Slowsort.
    """
    _slowsort(a, 0, len(a) - 1)

算法的基本分析得出 T(n) = 2T(n/2) + T(n-1)，但此后我无法解决递推关系。有人可以展示如何分析这种类型的功能吗？