int size = 256;
int arr[] = new int[size];

int w;
int RUN = 32;

class mem{


  int memarr[] = new int[size];
  int c = color(255);

  mem(){

    for(int i = 0; i < size; i++)
      memarr[i] = arr[i];

  }


}

ArrayList<mem> stages = new ArrayList<mem>();

void insertionSort(int array[], int left, int right) {

    for (int i = left + 1; i <= right; i++) {
        int temp = array[i];
        int j = i - 1;
        while (j >= left && array[j] > temp){
            array[j+1] = array[j];
            j--;

            stages.add(new mem());

        }
        array[j+1] = temp;
    }

}

void merge(int array[], int l, int m, int r)
{
    int len1 = m - l + 1;
    int len2 = r - m;
    //print(len1 + " " + len2);
    int left[] = new int[len1];
    int right[] = new int[len2];
    for (int i = 0; i < len1; i++)
        left[i] = array[l + i];
    for (int i = 0; i < len2; i++)
        right[i] = array[m + 1 + i];

    int i = 0;
    int j = 0;
    int k = l;

    while (i < len1 && j < len2)
    {
        if (left[i] <= right[j])
        {
            array[k] = left[i];
            i++;
        }
        else
        {
            array[k] = right[j];
            j++;
        }
        k++;
        stages.add(new mem());
    }

    while (i < len1)
    {
        array[k] = left[i];
        k++;
        i++;
        stages.add(new mem());
    }


    while (j < len2)
    {
        array[k] = right[j];
        k++;
        j++;
        stages.add(new mem());
    }
}

void timSort(int array[], int n)
{
    for (int i = 0; i < n; i+=RUN)
        insertionSort(array, i, min((i+31), (n-1)));

    for (int sizey = RUN; sizey < n; sizey = 2*sizey)
    {

        for (int left = 0; left < n; left += 2*sizey)
        {

            int mid = left + sizey - 1;
            print((left + 2*sizey - 1));
            print(" ");
            print(n-1);
            print(" ");
            print(mid);
            print("\n");
            int right = min((left + 2*sizey - 1), (n-1));


            merge(array, left, mid, right);
        }
    }
}

void setup(){

  size(1024,700);
  background(0);
  int r, temp;

  for(int i = 0; i < size; i++)
    arr[i] = i + 1;

  for(int i = 0; i < size; i++){
    r = floor(random(size));
    temp = arr[r];
    arr[r] = arr[i];
    arr[i] = temp;
  }

  w = width/size;

  timSort(arr,size);

  frameRate(240);

}

int stage = 0;

void draw(){

  background(0);
  strokeWeight(1);
  stroke(127);
  fill(255);
  translate(0,height);

  for(int i = 0; i < size; i++)
    rect(i*w,0,w,-float(stages.get(stage).memarr[i])/float(size)*height);

  if(stage < stages.size() - 1)
    stage += 1;

}