// IterativeQuicksort.java
// By David Kosbie

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class IterativeQuickSort {

   /////////////////////////////////////////
   // Iterative quicksort
   /////////////////////////////////////////

   // version 5 with insertionSort for ranges <= 7
   public static void iterativeQuicksort6(int[] a) {
      int[] range = new int[a.length+1]; // if (range[i]<0) then skip[i] = |range[i]|
      range[0] = a.length-1;
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (range[i] >= i) {
            j = range[i];
            if (j-i < 7) {
              // selectionsort the elements from a[i] to a[j] inclusive
              // and set all their ranges to -((j+1)-k)
              for (int m=i; m<=j; m++) {
                for (int n=m; n>i && a[n-1]>a[n]; n--)
                  swap(a, n, n-1);
                range[m] = -((j+1)-m);
                sortedCount++;
              }
              i = j;
            }
            else {
              for ( ; i<=j; i++) {
                int p = partition(a,i,j);
                sortedCount++;
                if (p > i) range[i] = p-1;
                if (p < j) range[p+1] = j;
                range[i = p] = -1; // sorted
              }
            }
          }
          else {
            // skip[i] += skip[i + skip[i]];
            while ((j = range[i-range[i]]) < 0) range[i] += j;
            i += -range[i]-1;
          }
      }
   }

   public static void iterativeQuicksort5(int[] a) {
      int[] range = new int[a.length+1]; // if (range[i]<0) then skip[i] = |range[i]|
      range[0] = a.length-1;
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (range[i] >= i) {
            j = range[i];
            for ( ; i<=j; i++) {
              int p = partition(a,i,j);
              sortedCount++;
              if (p > i) range[i] = p-1;
              if (p < j) range[p+1] = j;
              range[i = p] = -1; // sorted
            }
          }
          else {
            // skip[i] += skip[i + skip[i]];
            while ((j = range[i-range[i]]) < 0) range[i] += j;
            i += -range[i]-1;
          }
      }
   }

   public static void iterativeQuicksort4(int[] a) {
      int[] skip = new int[a.length+1];
      int[] range = new int[a.length];
      range[0] = a.length-1;
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (range[i] >= i) {
            j = range[i];
            for ( ; i<=j; i++) {
              int p = partition(a,i,j);
              sortedCount++;
              if (p > i) range[i] = p-1;
              range[p] = -1; // sorted
              if (p < j) range[p+1] = j;
              skip[i = p] = 1;
            }
          }
          else {
            // skip[i] += skip[i + skip[i]];
            while ((j = skip[i+skip[i]]) > 0) skip[i] += j;
            i += skip[i]-1;
          }
      }
   }

   public static void iterativeQuicksort3(int[] a) {
      int[] skip = new int[a.length+1];
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (skip[i] == 0) {
            for (j=i; (j<a.length-1) && (skip[j+1] == 0); j++) ;
            for ( ; i<=j; i++) {
              skip[i = partition(a,i,j)] = 1;
              sortedCount++;
            }
          }
          else {
            // skip[i] += skip[i + skip[i]];
            while ((j = skip[i+skip[i]]) > 0) skip[i] += j;
            i += skip[i]-1;
          }
      }
   }

   public static void iterativeQuicksort2(int[] a) {
      boolean[] sorted = new boolean[a.length];
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (!sorted[i]) {
            for (j=i; (j<a.length-1) && (!sorted[j+1]); j++) ;
            for ( ; i<=j; i++) {
              sorted[i = partition(a,i,j)] = true;
              sortedCount++;
            }
          }
      }
   }

   public static void iterativeQuicksort1(int[] a) {
      boolean[] sorted = new boolean[a.length];
      int i, j, sortedCount = 0;
      while (sortedCount < a.length) {
        for (i=0; i<a.length; i++)
          if (!sorted[i]) {
            for (j=i; (j<a.length-1) && (!sorted[j+1]); j++) ;
            sorted[i = partition(a,i,j)] = true;
            sortedCount++;
          }
      }
   }

   /////////////////////////////////////////
   // Pseudo-iterative quicksort
   /////////////////////////////////////////

    public static void pseudoIterativeQuicksort1(int[] a) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        stack.push(a.length-1);
        while (!stack.isEmpty()) {
          int right = stack.pop();
          int left = stack.pop();
          if (right > left) {
            int i = partition(a, left, right);
            stack.push(left);
            stack.push(i-1);
            stack.push(i+1);
            stack.push(right);
          }
        }
    }

    public static void pseudoIterativeQuicksort2(int[] a) {
        int[] stack = new int[2*a.length];
        int stackTop = 0;
        stack[stackTop++] = 0;
        stack[stackTop++] = a.length-1;
        while (stackTop > 0) {
          int right = stack[--stackTop];
          int left = stack[--stackTop];
          if (right > left) {
            int i = partition(a, left, right);
            stack[stackTop++] = left;
            stack[stackTop++] = i-1;
            stack[stackTop++] = i+1;
            stack[stackTop++] = right;
          }
        }
    }

    public static void pseudoIterativeQuicksort3(int[] a) {
        int[] stack = new int[2*a.length];
        int stackTop = 0;
        stack[stackTop++] = 0;
        stack[stackTop++] = a.length-1;
        while (stackTop > 0) {
          int right = stack[--stackTop];
          int left = stack[--stackTop];
          while (right > left) {
            int i = partition(a, left, right);
            if (i-1 > left) {
              stack[stackTop++] = left;
              stack[stackTop++] = i-1;
            }
            left = i+1;
          }
        }
    }

   /////////////////////////////////////////
   // Recursive quicksort, adapted from:
   // Sedgewick and Wayne, Introduction to Programming in Java
   // http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
   /////////////////////////////////////////

    public static void recursiveQuicksort(int[] a) {
        // shuffle(a);                        // to guard against worst-case
        recursiveQuicksort(a, 0, a.length - 1);
    }

    // quicksort a[left] to a[right]
    public static void recursiveQuicksort(int[] a, int left, int right) {
        if (right <= left) return;
        int i = partition(a, left, right);
        recursiveQuicksort(a, left, i-1);
        recursiveQuicksort(a, i+1, right);
    }

    // partition a[left] to a[right], assumes left < right
    private static int partition(int[] a, int left, int right) {
        // DK:  added check if (left == right):
        if (left == right) return left;
        int i = left - 1;
        int j = right;
        while (true) {
            while (a[++i] < a[right])       // find item on left to swap
                ;                           // a[right] acts as sentinel
            while (a[right] < a[--j])       // find item on right to swap
                if (j == left) break;       // don't go out-of-bounds
            if (i >= j) break;              // check if pointers cross
            swap(a, i, j);                  // swap two elements into place
        }
        swap(a, i, right);                  // swap with partition element
        return i;
    }

    private static void shuffle(int[] a) {
        // DK: using random.nextInt seems faster than Math.random()
        Random random = new Random();
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + random.nextInt(n-i);   // between i and n-1
            // int r = i + (int) (Math.random() * (n-i));   // between i and n-1
            swap(a, i, r);
        }
    }

    public static void swap(int[] a, int i, int j) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }



   /////////////////////////////////////////
   // Iterative mergeSort
   /////////////////////////////////////////

   public static void iterativeMergesort(int[] a) {
      int[] aux = new int[a.length];
      for (int blockSize=1; blockSize<a.length; blockSize*=2)
         for (int start=0; start<a.length; start+=2*blockSize)
            merge(a, aux, start, start+blockSize, start+2*blockSize);
   }

   /////////////////////////////////////////
   // Iterative mergeSort without copy
   /////////////////////////////////////////

   public static void iterativeMergesortWithoutCopy(int[] a) {
      int[] from = a, to = new int[a.length];
      for (int blockSize=1; blockSize<a.length; blockSize*=2) {
         for (int start=0; start<a.length; start+=2*blockSize)
            mergeWithoutCopy(from, to, start, start+blockSize, start+2*blockSize);
          int[] temp = from;
          from = to;
          to = temp;
      }
       if (a != from)
         // copy back
         for (int k = 0; k < a.length; k++)
            a[k] = from[k];
   }

    private static void mergeWithoutCopy(int[] from, int[] to, int lo, int mid, int hi) {
       // DK: cannot just return if mid >= a.length, but must still copy remaining elements!
       // DK: add two tests to first verify "mid" and "hi" are in range
       if (mid > from.length) mid = from.length;
       if (hi > from.length) hi = from.length;
       int i = lo, j = mid;
       for (int k = lo; k < hi; k++) {
          if      (i == mid)          to[k] = from[j++];
          else if (j == hi)           to[k] = from[i++];
          else if (from[j] < from[i]) to[k] = from[j++];
          else                        to[k] = from[i++];
       }
       // DO NOT copy back
       // for (int k = lo; k < hi; k++)
       //   a[k] = aux[k];
    }

   /////////////////////////////////////////
   // Recursive mergeSort, adapted from:
   // Sedgewick and Wayne, Introduction to Programming in Java
   // http://www.cs.princeton.edu/introcs/42sort/MergeSort.java.html
   /////////////////////////////////////////

    private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
       // DK: add two tests to first verify "mid" and "hi" are in range
       if (mid >= a.length) return;
       if (hi > a.length) hi = a.length;
       int i = lo, j = mid;
       for (int k = lo; k < hi; k++) {
          if      (i == mid)     aux[k] = a[j++];
          else if (j == hi)      aux[k] = a[i++];
          else if (a[j] < a[i])  aux[k] = a[j++];
          else                   aux[k] = a[i++];
       }
       // copy back
       for (int k = lo; k < hi; k++)
          a[k] = aux[k];
    }

    public static void recursiveMergesort(int[] a, int[] aux, int lo, int hi) {
       // base case
       if (hi - lo <= 1) return;
       // sort each half, recursively
       int mid = lo + (hi - lo) / 2;
       recursiveMergesort(a, aux, lo, mid);
       recursiveMergesort(a, aux, mid, hi);
       // merge back together
       merge(a, aux, lo, mid, hi);
    }

    public static void recursiveMergesort(int[] a) {
        int n = a.length;
        int[] aux = new int[n];
        recursiveMergesort(a, aux, 0, n);
    }

   /////////////////////////////////////////
   // Built-in sort from java.util.Arrays.sort
   /////////////////////////////////////////

    public static void sort(int[] a) {
      sort1(a, 0, a.length);
    }

    private static void sort1(int x[], int off, int len) {
      // Insertion sort on smallest arrays
      if (len < 7) {
        for (int i=off; i<len+off; i++)
          for (int j=i; j>off && x[j-1]>x[j]; j--)
            swap(x, j, j-1);
          return;
      }

      // Choose a partition element, v
      int m = off + (len >> 1);       // Small arrays, middle element
      if (len > 7) {
          int l = off;
          int n = off + len - 1;
          if (len > 40) {        // Big arrays, pseudomedian of 9
        int s = len/8;
        l = med3(x, l,     l+s, l+2*s);
        m = med3(x, m-s,   m,   m+s);
        n = med3(x, n-2*s, n-s, n);
          }
          m = med3(x, l, m, n); // Mid-size, med of 3
      }
      int v = x[m];

      // Establish Invariant: v* (<v)* (>v)* v*
      int a = off, b = a, c = off + len - 1, d = c;
      while(true) {
        while (b <= c && x[b] <= v) {
          if (x[b] == v)
              swap(x, a++, b);
          b++;
        }
        while (c >= b && x[c] >= v) {
          if (x[c] == v)
              swap(x, c, d--);
          c--;
        }
        if (b > c)
          break;
        swap(x, b++, c--);
      }

      // Swap partition elements back to middle
      int s, n = off + len;
      s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
      s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      // Recursively sort non-partition-elements
      if ((s = b-a) > 1)
          sort1(x, off, s);
      if ((s = d-c) > 1)
          sort1(x, n-s, s);
    }

    private static void vecswap(int x[], int a, int b, int n) {
      for (int i=0; i<n; i++, a++, b++)
        swap(x, a, b);
    }

    private static int med3(int x[], int a, int b, int c) {
      return (x[a] < x[b] ?
        (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
        (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
    }

   /////////////////////////////////////////
   // Main and support methods
   /////////////////////////////////////////

   public static void main(String[] args) {
      System.out.println("First, verify this actually sorts arrays...");
      int n = 17; // pick a size to suit you!
      int[] a = makeRandomArray(n);
      int[] acopy = copyArray(a); // use to verify sort using built-in sort
      System.out.println("Before: " + Arrays.toString(a));
      pseudoIterativeQuicksort3(a);
      System.out.println("After: " + Arrays.toString(a));
      // now verify the sort worked by comparing to built-in sort
      Arrays.sort(acopy);
      System.out.println("Verified = " + (Arrays.equals(a, acopy)));

      n = 2*1000*1000; // 1m feels about right
      long time0, time1;
      System.out.println("\nNow, compare times on array of size " + n + ":");
      a = makeRandomArray(n);
      System.out.print("iterativeMergesort: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeMergesort(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeMergesortWithoutCopy: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeMergesortWithoutCopy(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("recursiveMergesort: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      recursiveMergesort(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.println();

      System.out.print("iterativeQuicksort1: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort1(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeQuicksort2: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort2(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeQuicksort3: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort3(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeQuicksort4: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort4(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeQuicksort5: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort5(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("iterativeQuicksort6: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      iterativeQuicksort6(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.println();

      System.out.print("pseudoIterativeQuicksort1: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      pseudoIterativeQuicksort1(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("pseudoIterativeQuicksort2: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      pseudoIterativeQuicksort2(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("pseudoIterativeQuicksort3: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      pseudoIterativeQuicksort3(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.println();

      System.out.print("recursiveQuicksort:    ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      recursiveQuicksort(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("sort from Arrays.sort: ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      sort(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");

      System.out.print("Actual Arrays.sort:    ");
      acopy = copyArray(a);
      time0 = System.currentTimeMillis();
      Arrays.sort(acopy);
      time1 = System.currentTimeMillis();
      System.out.println((time1-time0) + "milliseconds");
   }

   public static int[] copyArray(int[] a) {
      int[] copy = new int[a.length];
      System.arraycopy(a, 0, copy, 0, a.length);
      return copy;
   }

   public static int[] makeRandomArray(int n) {
      int[] a = new int[n];
      Random random = new Random();
      for (int i=0; i<a.length; i++)
         // use small #'s for small n for "pretty printing"
         a[i] = ((n < 100) ? random.nextInt(100) : random.nextInt());
      return a;
   }
}