Quick Sort

quick-sort.h

#include <vector>

using std::vector;

template<typename T>
void exchange(vector<T>& list, int i, int j)
{
	T temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

template<typename T>
int partition(vector<T>& list, int low, int high)
{
  int left = low;
  int right = high + 1;
  T pivot = list[low]; // arbitrarily pick low as pivot value

  while (true) // loop until left and right meet
  {
    while (list[++left] < pivot) // update left until it hits out of place
    {
      if (left == high)
      {
        break;
      }
    }

    while (pivot < list[--right]) // update right until it hits out of place
    {
      if (right == low)
      {
        break;
      }
    }

    if (left >= right) // break when pointers meet
    {
      break;
    }

    exchange(list, left, right); // put lesser and greater on proper sides
  }

  exchange(list, low, right); // move pivot value into pivot position
  return right;
};

template<typename T>
void sort(vector<T>& list, int low, int high)
{
  if (high <= low) // base case
  {
	  return;
	}
		
	const int mid = partition(list, low, high);
	sort(list, low, mid - 1);
	sort(list, mid + 1, high);
}

/**
 * Where the merge sort begins by sorting sub-lists
 * and then combines the results, the quick sort
 * sorts the main list and then proceeds to sort
 * the sub-lists. It does this by partioning
 * the list at a pivot, ensuring that the pivot
 * is positioned such that it is greater than all
 * preceding elements and lesser than all following
 * elements. This method recurses to bottom, until
 * all elements are in their proper place. This
 * method also achieves linearithmic complexity (O(nlogn))
 * and it is favored for its simplicity.
 */
template<typename T>
void quick_sort(vector<T>& list)
{
  sort(list, 0, list.size() - 1);
}