Sorting? Awesome fun for whole family

Bubble sort is dumb. Let's look at quick sort and merge sort.

Quick sort:

• O(nlogn) best and average.
• Worst case is O(n^2)
• divide and conquer mother fucker
• probably not stable (same keys may change order)
• pick a pivot, p, in the array (usually in the middle)
• partition into two arrays, one with all values <= p, the other with all values >= p
• the partition step can be done in place
• call quicksort on the two arrays
• if the array size is zero, you're done

template  void qs2 (vector&; arr, int left, int right)
{
 if (left >= right)
  return;

 int i = left, j = right;

    int pivot = arr[(left + right) / 2];
     
    while (i <= j) {
        while (arr[i] < pivot)
                i++;
        while (arr[j] > pivot)
                j--;
        if (i <= j) {
  swap(arr[i], arr[j]);
                i++;
                j--;
        }  
    };

 qs2(arr, left, i - 1);
 qs2(arr, i + 1, right);
}

Now let's try some mergesort:

• worst case is O(nlogn)
• better for using slower data access things like files, tape drives
• don't have to store everything in memory

template  void mergeSort (vector& v)
{
 if (v.size() < 2) return;
 // first divide in two, until only size 1 left
 int n = v.size(); 
 int middle = n / 2;
 vector left;
 left.insert(left.begin(), v.begin(), v.begin() + middle);

 vector right;
 right.insert(right.begin(), v.begin() + middle, v.end());

 mergeSort(left);
 mergeSort(right);

 v.clear();

 // then reconstitute such that the new result is in order
 while (left.size() > 0 || right.size() > 0)
 {
  if (left.size() > 0 && right.size() > 0)
  {
   if (left[0] <= right[0])
   {
    v.push_back(left.front());
    left.erase(left.begin());
   }
   else
   {
    v.push_back(right.front());
    right.erase(right.begin());
   }
  }
  else if (left.size() > 0)
  {
   v.insert(v.end(), left.begin(), left.end());
   left.clear();
  }
  else if (right.size() > 0)
  {
   v.insert(v.end(), right.begin(), right.end());
   right.clear();
  }
 }
}