package com.jcomeau;
// algorithms from Quicksort entry at Wikipedia
class IntArraySort {
 public static void quicksort(int[][] array, int left, int right) {
  // sort by length of subarrays
  if (right > left) {
   int pivotIndex = getPivot(array, left, right);
   int pivotNewIndex = partition(array, left, right, pivotIndex);
   quicksort(array, left, pivotNewIndex - 1);
   quicksort(array, pivotNewIndex + 1, right);
  }
 }
 public static int getPivot(int[][] array, int left, int right) {
  return left + (right - left) / 2; // FIXME: optimize
 }
 public static void swap(int[][] array, int a, int b) {
  int[] subarray;
  subarray = array[b];
  array[b] = array[a];
  array[a] = subarray;
 }
 public static int partition(int[][] array,
  int left, int right, int pivotIndex) {
  int pivotValue = array[pivotIndex].length;
  int storeIndex = left;
  swap(array, pivotIndex, right);
  for (int i = left; i < right - 1; i++)
   if (array[i].length < pivotValue) swap(array, storeIndex++, i);
  swap(array, right, storeIndex);
  return storeIndex;
 }
 public static void main(String[] args) {
  if (Common.DEBUGGING) {
   int[][] testarray = {
    {3003, 110, 11, 1},
    {2002, 3},
    {3113, 220, 22},
    {1001, 330, 30, 3},
    {4444, 4},
   };
   System.out.println("Array before sorting:");
   for (int i = 0; i < testarray.length; i++) {
    for (int j = 0; j < testarray[i].length; j++) {
     System.out.print(" " + testarray[i][j]);
    }
    System.out.println();
   }
   quicksort(testarray, 0, testarray.length - 1);
   System.out.println("Array after sorting:");
   for (int i = 0; i < testarray.length; i++) {
    for (int j = 0; j < testarray[i].length; j++) {
     System.out.print(" " + testarray[i][j]);
    }
    System.out.println();
   }
  }
 }
}