HeapSort/IntrospectiveSort on Array Portion Java implementation

Question

I am currently studying sorting algorithms and need to implement HeapSort and Introspective Sort.

I think I have implemented HeapSort successfully (the code works, tried on millions of random arrays with random sizes, always worked), here's my code:

  public static <T extends Comparable<? super T>> void hsort(T[] a) {
    int n = a.length;
    if(n < 2) return;
    /* Heapify */
    for(int i = (n-2)/2; i >= 0; i--)
      moveDown(a, i, n);
    for(int i = n-1; i > 0; i--) {
      swap(a, 0, i);
      moveDown(a, 0, i);
    }
  }

And the moveDown code is:

private static <T extends Comparable <? super T>> void moveDown(T[] a, int i, int max) {
    T e = a[i];
    int j;  /* Son index */
    while((j = (2*i)+1) < max) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

These 2 methods shuold work completely fine, I have tested them multiple times and I never encountered any problem.

I am also trying to start from those 2 methods and implement Introspective Sort, my code is something like this:

public static <T extends Comparable<? super T>> void introSort(T[] a) {
    int size = a.length;
    if(size < 2) return;
    int log = Integer.SIZE - Integer.numberOfLeadingZeros(size);
    introSort(a, 0, size-1, 2*log);
  }

private static <T extends Comparable<? super T>> void introSort(T[] a, int min, int max, int lev) {
    if(max - min < ISORT_THRESHOLD) isort(a, min, max); // Small intervall
    else if(lev == 0) hsortAux(a, min, max); // HeapSort on Array Portion
    else {
      // QuickSort
      while (min < max) {
        lev--;
        /* Tukey approximation */
        int t = tukeyApproximation(a, min, max-1);
        //t = min; Ignore this for now and read below this code
        T p = a[t];
        int i = min, j = max;
        do {
          while(a[i].compareTo(p) < 0) i++;
          while(a[j].compareTo(p) > 0) j--;
          if(i <= j) {
            swap(a, i, j);
            i++; j--;
          }
        } while(i <= j);
        introSort(a, min, j, lev);
        min = i;
      }
    }
  }

I think that the code above is fine too assuming that the methods isort and hsortAux work fine. On my testing I noticed that it only fails when the heapsort is called. The code should work (the target is to make it work) both when I use the tukey approximation to determine the pivot index and when I choose a random pivot like for example always the first element of the array. The partitioning with the QuickSort should be correct because I have tried many quicksort implementation and they all work and, as I already said, the code works when heapsort is not called. The partitioning is actually a copypaste from a quicksort in another method which works perfectly.

I know for sure that the methods isort and tukeyApproximation work as intended because I have tested them alone and on quicksort implementations and they work just fine.

However I don't seem to be capable of implementing a heapsort (the method called hsortAux) that does its job only on an array portion between min and max. I have spent several hours looking for an answer here and on Google, I have tried to implement my own version by looking at others people's code but I have failed multiple times and here I am wasting your time :). Once I managed to make a working heapSort but it didn't seem to work when the pivot was not chosen by the tukey approximation (e.g. the first element of the array or a random one in the portion).

Here is my current hsortAux code, derived from the origianl hsortAux:

private static <T extends Comparable<? super T>> void hsortAux(T[] a, int min, int max) {
    for(int i = (min + max - 1)/2 ; i >= min; i--)
      moveDownAux(a, min, i, max+1);
    for(int i = max; i > min; i--) {
      swap(a, min, i);
      moveDownAux(a, min, min, i);
    }
  }

moveDownAux is supposed to be the moveDown method that only works on an array portion however I really have no idea how to implement it, I have tried to use the previous moveDown method instead but it obviously doesn't work at all. When implementing moveDownAux I'm not even sure I need the variable called min.

Here is my current moveDownAux method:

private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
    T e = a[i];
    int j;  /* Son */
    while((j = (2*i)+1) < max-1) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest Son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

Thanks in advance for your time and answers

Answer 1

So after few weeks of pain I managed to understand what was wrong. Everything seems to work fine with the following moveDownAux method:

private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
    T e = a[i];
    int j;
    while((j = (2*i)+1 - min) < max) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

All I did in the end was change the while condition, I'm still trying to figure out why now it works and before it didn't.

Thanks to everyone