Алгоритм типа Bubble / Merge: необходимо подтверждение исправления

Question

Получил этот алгоритм, который является разновидностью пузырьковой сортировки. Как можно доказать его правильность? Желательно благодаря сильной индукции. Любые указатели оценены!

Answer 1

Предположим, что временная сложность some_sort(A) равна T(n).

some_sort (Array a, a + mid)

Сложность времени: T (n /2)

some_sort (Array, b-mid, b)

Сложность времени: T (n / 2)

some_sort (Array, a + (mid + 1) // 2, b - (mid + 1) // 2)

Сложность времени: T (n / 2)

---

for i in range(n):
    some_sort(Array a, a + mid)                      # Will be called n times.
    some_sort(Array, b-mid, b)                       # Will be called n times.
    some_sort(Array, a + (mid+1)//2, b - (mid+1)//2) # Will be called n times.

T(n) = n * T(n / 2) + n * T(n / 2) + n * T(n / 2) + O(1)
T(n) = 3 * n * T(n / 2) + O(1)

Используя теорему мастеров, получаем:

T(n) = n^log2(3 * n)