#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000000
#define MIN_LEN 20
#define MAX_LEN 50
#define MAX_CHAR 'd'

void tsort(char **s, int lo, int hi, int pos) {
  if (lo >= hi) {
    return;
  }

  int curr = lo, left = lo, right = hi;
  char mid = (s[lo][pos] + s[hi][pos]) / 2;
  char *tmp;

  while (curr <= right) {
    char c = s[curr][pos];
    if (c < mid) {
	    if (curr > left) {
        tmp = s[curr];
        s[curr] = s[left];
        s[left] = tmp;
	    }
	    left++;
	    curr++;
    } else if (c > mid)	{
      tmp = s[curr];
      s[curr] = s[right];
      s[right] = tmp;
	    right--;
    }	else {
	    curr++;
    }
  }

  tsort(s, lo, left - 1, pos);
  if (s[left][pos] != '\0' ) {
    tsort(s, left, right, pos + 1);
  }
  tsort(s, right + 1, hi, pos);
}

int main(void) {
  srand(time(NULL));
  char* s[N];

  // Generate some strings
  for (int i = 0; i < N; i++) {
    int len = rand() % (MAX_LEN - MIN_LEN + 1) + MIN_LEN;
    s[i] = (char*) malloc(len + 1);
    for (int j = 0; j < len; j++) {
      s[i][j] = rand() % (MAX_CHAR - 'a' + 1) + 'a';
    }
    s[i][len] = '\0';
  }

  tsort(s, 0, N - 1, 0);

  // Print them
  // for (int i = 0; i < N; i++) {
  //   printf("[%s]\n", s[i]);
  // }
}