mergesort java collections framework impl.

gistfile1.java

 private static void sort(int start, int end, long[] array) {
           long temp;
           int length = end - start;
           if (length < 7) {
               for (int i = start + 1; i < end; i++) {
                   for (int j = i; j > start && array[j - 1] > array[j]; j--) {
                       temp = array[j];
                       array[j] = array[j - 1];
                       array[j - 1] = temp;
                   }
               }
               return;
           }
           int middle = (start + end) / 2;
           if (length > 7) {
               int bottom = start;
               int top = end - 1;
               if (length > 40) {
                   length /= 8;
                   bottom = med3(array, bottom, bottom + length, bottom
                           + (2 * length));
                   middle = med3(array, middle - length, middle, middle + length);
                   top = med3(array, top - (2 * length), top - length, top);
               }
               middle = med3(array, bottom, middle, top);
           }
           long partionValue = array[middle];
           int a, b, c, d;
           a = b = start;
           c = d = end - 1;
           while (true) {
               while (b <= c && array[b] <= partionValue) {
                   if (array[b] == partionValue) {
                       temp = array[a];
                       array[a++] = array[b];
                       array[b] = temp;
                   }
                   b++;
               }
               while (c >= b && array[c] >= partionValue) {
                   if (array[c] == partionValue) {
                       temp = array[c];
                       array[c] = array[d];
                       array[d--] = temp;
                   }
                   c--;
               }
               if (b > c) {
                   break;
               }
               temp = array[b];
               array[b++] = array[c];
               array[c--] = temp;
           }
           length = a - start < b - a ? a - start : b - a;
           int l = start;
           int h = b - length;
           while (length-- > 0) {
               temp = array[l];
               array[l++] = array[h];
               array[h++] = temp;
           }
           length = d - c < end - 1 - d ? d - c : end - 1 - d;
           l = b;
           h = end - length;
           while (length-- > 0) {
               temp = array[l];
               array[l++] = array[h];
               array[h++] = temp;
           }
           if ((length = b - a) > 0) {
               sort(start, start + length, array);
           }
           if ((length = d - c) > 0) {
               sort(end - length, end, array);
           }
       }