mergesort

Mam takie zdanie z książki

Top-down mergesort uses between ½ N lg N and N lg N compares to
sort any array of length N.

I nie bardzo kumam o co chodzi.

    for (int k = lo; k <= hi; k++) {
    int i = lo, j = mid+1;
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];

O jakie compares chodzi ? O less ? Czy ogólnie i > mid itp. Przepraszam że zadaje głupie pytania.

Mergesort wykonuje miedzy 1/2nlogn a nlogn porownan miedzy elementami tablicy. Czyli jest big teta od n. Otworz CLRS albo Zajrzyj tutaj: https://algs4.cs.princeton.edu/22mergesort/

Czyli chodzi o less(aux[j], aux[i])) . Liczyłem te operacje na kodzie. Liczba porównań dla less wynosi co maksymalnie 1/2nlgn. Liczba porównań dla wszystkich operacji jak if (i > mid) itd wynosi zawsze nlgn.
Nadal nie czaję. Mam przy okazji takie pytanie. Czy aby posługiwać się algorytmami to trzeba znać te wszystkie dowody przez indukcje itp.

Introduction to Algorithms to ciężkostrawna książka. Wybrałem Algorithms Sedgewicka.

To Wez tego Sedgwick'a to Ci sie rozjasni. Wypadaloby znac dowody, to pozwala zrozumiec algorytm.

Skopałem kod. I źle liczy. Teraz jest ok.