Number of array accesses in ascending merge sort?

Question

Java

The book "Algorithms in Java" says that descending (recursive) and ascending (iterative) merge sort performs a maximum of 6N * lg (N) (binary logarithm) accesses to the array. In one of the exercises, it is proposed to check this by drawing a graph of the number of accesses to the array versus N . Descending sorting is fine, but ascending sorting gives strange results.
Here is the graph for N = 1..512. The red line is 6N*lg(N) and the black one is the actual array accesses.

As can be seen in some places, the black line suddenly increases. I noticed that this often happens when N = 2^x + 1.
I don’t understand what the problem is, here is my code (the implementation of the sort itself is completely from the book):

public class MergeBUCount {

    private static Integer count; // переменная для счета обращений к массиву

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
            count += 2; //по два обращения к массиву
        }
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              {a[k] = aux[j++]; count += 2;} 
            else if (j > hi)               {a[k] = aux[i++]; count += 2;}
            else if (less(aux[j], aux[i])) {a[k] = aux[j++]; count += 4;}//обращения при сравнении + копировании
            else                           {a[k] = aux[i++]; count += 4;}
        }

    }
    public static void sort(Comparable[] a, int size) {
        int N = size;
        Comparable[] aux = new Comparable[N];
        for (int n = 1; n < N; n = n+n) {
            for (int i = 0; i < N-n; i += n+n) {
                int lo = i;
                int m  = i+n-1;
                int hi = Math.min(i+n+n-1, N-1);
                merge(a, aux, lo, m, hi);
            }
        }
    }

  public static void main(String[] args) {
                 Integer[] a = new Integer[N];
    //инициализация и тд...

    for (int i = 1; i <= N; i++) {
      StdRandom.shuffle(a); //перемешиваем массив
      count = 0;
      sort(a, i);

      double limit =  6 * i * (Math.log(i) / Math.log(2)); //граничное значение

      StdDraw.setPenColor(StdDraw.BLACK);
      StdDraw.point(i, count); //фактическая точка

      StdDraw.setPenColor(StdDraw.RED);
      StdDraw.point(i, limit); //граничная точка
    }
  }

Answer 1

well, what's the problem then?
the graph is drawn up for the general case, in fact it will be clear that it will differ.
you have different code branches in your code that give a different number of hits.