HeapSort/IntrospectiveSort on Array Portion Java implementation -

i studying sorting algorithms , need implement heapsort , introspective sort.

i think have implemented heapsort (the code works, tried on millions of random arrays random sizes, worked), here's code:

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

and 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];       = j;     }     a[i] = e;   } 

these 2 methods shuold work fine, have tested them multiple times , never encountered problem.

i trying start 2 methods , implement introspective sort, code 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 , read below code         t p = a[t];         int = min, j = max;         {           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 code above fine assuming methods isort , hsortaux work fine. on testing noticed fails when heapsort called. code should work (the target make work) both when use tukey approximation determine pivot index , when choose random pivot example first element of array. partitioning quicksort should correct because have tried many quicksort implementation , work and, said, code works when heapsort not called. partitioning copypaste quicksort in method works perfectly.

i know sure methods isort , tukeyapproximation work intended because have tested them alone , on quicksort implementations , work fine.

however don't seem capable of implementing heapsort (the method called hsortaux) job on array portion between min , max. have spent several hours looking answer here , on google, have tried implement own version looking @ others people's code have failed multiple times , here wasting time :). once managed make working heapsort didn't seem work when pivot not chosen tukey approximation (e.g. first element of array or random 1 in portion).

here current hsortaux code, derived origianl hsortaux:

private static <t extends comparable<? super t>> void hsortaux(t[] a, int min, int max) {     for(int = (min + max - 1)/2 ; >= min; i--)       movedownaux(a, min, i, max+1);     for(int = max; > min; i--) {       swap(a, min, i);       movedownaux(a, min, min, i);     }   } 

movedownaux supposed movedown method works on array portion have no idea how implement it, have tried use previous movedown method instead doesn't work @ all. when implementing movedownaux i'm not sure need variable called min.

here 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];       = j;     }     a[i] = e;   } 

thanks in advance time , answers

so after few weeks of pain managed understand wrong. seems work fine 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];       = j;     }     a[i] = e;   } 

all did in end change while condition, i'm still trying figure out why works , before didn't.

thanks everyone