Advanced Programming I Lecture Notes

2 February 2006 • Faster Sorting

template <typename T>
size_t
partition(T a[], size_t left, size_t right) {

  assert(left < right);

  T pivot = a[left];
  size_t l = left + 1;

  // a[l .. l - 1] ≤ pivot < a[right .. right' - 1]

  while (l < right)
    if (a[l] ≤ pivot) l++;
    else if (pivot < a[right - 1]) right--;
    else std::swap(a[l++], a[--right]);

  std::swap(a[left], a[--l]);
  return l;
  }

This page last modified on 24 January 2006.