Количество сравнений для оптимизированной сортировки слиянием в уже отсортированном массиве

Question

Хотелось бы узнать, как я могу рассчитать количество сравнений для оптимизированной сортировки слиянием, описанной ниже, для уже отсортированного массива.

Это похоже на обычную сортировку слиянием, но не «объединяет»если два подмассива уже отсортированы.

mergesort(arr, auxArr, lo, hi)
  if (hi <= lo) return;
  mid = lo + (hi + lo) / 2

  sort(arr, auxArr, lo, mid)
  sort(arr, auxArr, mid+1, hi)

  if (less(arr[mid], arr[mid+1]) return; // optimization
  merge(arr, auxArr, lo, mid ,hi)

Вот моя попытка узнать количество сравнений

1. Пусть C (N) будет числом сравнений
2. C (N) = 2 * C (N / 2) + 1 (количество сравнений для сортировки двух подмассивов + 1 сравнение для нашей оптимизации)
3. Использование отношения повторения,

---

C(N) = = 2 * C(N/2) + 1
= 2 ( 2C(N/4) + 1 ) + 1
= 4 C(N/4) + 1 + y
...
= N C(N/N) + 1 + 2 + 4 + ... + 2^(log2 (N/2))
= 1 + 2 + 4 + ... + 2^(log2 (N/2))

Но ответ говорит, что это ~ log2 (N), и я застрял.Есть идеи?