import java.util.Random;


public class Test {



  public static void main(String[] args) {
    final int N = 50000000;
int[] array = new int[N];
Random rng = new Random();// fill with random values
for (int counter = 0; counter < N; counter++) {
array[counter] = rng.nextInt(N);
//System.out.println(counter + " " + array[counter]);
}
quicksort(array, 0, array.length - 1); // quicksort entire array
for (int counter = 0; counter < N; counter++) { // check result
//System.out.println(counter + " " + array[counter]);
}

  }

  public static void quicksort(int[] array, int lo, int hi) {
if (lo < hi) { // if lo and hi have not become equal..
int p = partition(array, lo, hi); // split. p is the split point
quicksort(array, lo, p); // quicksort lower half
quicksort(array, p + 1, hi); // quicksort upper half
}
}
  static int partition(int[] array, int lo, int hi) {
// work on array from index lo to hi
int pivot = array[lo]; // pivot is lowest element in section
int i = lo - 1; // i and j are 2 moving pointers
int j = hi + 1; // i will increase and j decrease
while (true) { // we break out by returning j
do { // move i up until find element bigger than pivot
i++;
} while (array[i] < pivot);
do { // move j down until find small element less than pivot
j--;
} while (array[j] > pivot);
if (i >= j) { // if they meet..
return j; // stop - we split at this position
}
int temp = array[i]; // else swap i and j elements
array[i] = array[j];
array[j] = temp; // then continue i up and j down
}
}

}