QSort in D: is this best?

downs default_357-line at yahoo.de
Sun Dec 20 04:17:29 PST 2009


Or are there any bugs/optimization opportunities I'm missing?

void qsort(T)(T[] array) {
  if (array.length < 2) return;
  static int i;
  auto pivot = array[i++%$];
  // from is base-0, to is base-1.
  int from = 0, to = array.length;
  while (from != to) {
    if (array[from] >= pivot && array[to-1] < pivot)
      swap(array[from], array[to-1]);
    if (array[from] < pivot)
      from ++;
    if (array[to-1] >= pivot)
      to --;
  }
  array[0 .. from].qsort();
  array[from .. $].qsort();
}



More information about the Digitalmars-d mailing list