Note:  This is a programming quiz.  You must use Visual C++.  You must begin with a new project, and you may not use any notes or any pre-written code.

Your task is to write the missing portions of the code below:  That is:
    bubbleSort(),
    merge(), and
    mergeSort().

Note that the comments for merge() and mergeSort() were not deleted.  You may use these comments if you wish, or delete them and use your own comments if you prefer.

Good luck.

// This program demonstrates the following 6 sorts:
// insertionSort, selectionSort, bubbleSort,
// mergeSort, quickSort, radixSort.

// The IntroCS students are responsible for the first 4
// sorts (all but quickSort and radixSort).

// The AP CS students are responsible for all 6 sorts.

//////////////////////////////////////////////////
/////  Includes, Typedefs, Constants
//////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <math.h>
#include "apvector.h"

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;
typedef int& intByReference;

const int BASE = 10;
const int MAX_EXPT = 6;

//////////////////////////////////////////////////
/////  loadVector(), printVector(), and swap()
//////////////////////////////////////////////////

// loadVector() loads the vector v with
// random elements in [0,BASE^MAX_EXPT)
// (presently 10^6).
void loadVector(intVectorByReference v)
{
 // load vector with numbers mostly random in [0,BIG_NUM]
 int len = v.length();
    for (int i = 0; i < len; i++)
        v[i] = rand() % int(pow(BASE,MAX_EXPT));
}

// This function is provided here for debugging purposes,
// and is not currently called by any functions below.
void printVector(intVectorByReference v)
{
 // print vector elements separated by two spaces with
 // a carriage return at the end
    for (int i = 0; i < v.length(); i++)
        cout << v[i] << "  ";
    cout << endl;
}

void swap(intByReference x, intByReference y)
{
 int temp;
 temp = x;
 x = y;
 y = temp;
}

//////////////////////////////////////////////////
/////  insertionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly inserts the element at the
// cursor into the sorted vector to the left of the cursor.

void insertionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=1; cursor<len; cursor++)
        for (i=0;i<cursor;i++)
            if (v[i] > v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  selectionSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly finds the smallest element from
// the cursor to the right end of the vector and swaps
// that element with the cursor.

void selectionSort(intVectorByReference v)
{
 int len, cursor, i;
 len = v.length();
    for (cursor=0; cursor<len-1; cursor++)
        for (i=cursor+1;i<len;i++)
            if (v[i] < v[cursor])
    swap(v[i],v[cursor]);
}

//////////////////////////////////////////////////
/////  bubbleSort()
//////////////////////////////////////////////////

// This O(n^2) sort repeatedly sweeps through the vector and
// swaps each pair of elements which are out of order.
// This is repeated until an entire sweep results in no swaps.

void bubbleSort(intVectorByReference v)
{
    // YOU WRITE THIS
}

//////////////////////////////////////////////////
/////  mergeSort()
//////////////////////////////////////////////////

// This O(n log n) sort is much faster than the O(n^2) sorts
// above.  It is also recursive whereas the above sorts are
// iterative.  It operates by recursively sorting the left
// and right halves of the vector and then merging the sorted
// halves into a sorted whole.

void merge(intVectorByReference v,int lo,int hi)
{
 // 1. Declare variables

 // 2. Initialize variables

 // 3. Merge into the mergeVector
    for (mergeIndex=0; mergeIndex<mergeSize; mergeIndex++)
    {
  // Get the next element from either left half or right half,
  // place into mergeVector and advance the appropriate index.
  // Use the left half if:
  //  a)  The right side is done, or
  //  b)  The left side is not done, and the left side is smaller
    }

 // 4. Copy from mergeVector back into v
}

// This function sorts the elements from v[lo] to v[hi].
void mergeSort(intVectorByReference v,int lo,int hi)
{
 // 1 Base Case: if there is 1 (or fewer) elements,
 // then the vector is sorted, so just return.

 // 2.  Recursive Case
    // Sort the left half
    // Sort the right half
    // And merge the sorted halves
}

void mergeSort(intVectorByReference v)
{
    mergeSort(v,0,v.length()-1);
}

//////////////////////////////////////////////////
/////  quickSort()
//////////////////////////////////////////////////

// This O(n log n) sort is also recursive like mergeSort.
// It is typically about twice as fast as mergeSort.  However,
// while the average performance for quickSort is O(n log n),
// its worst-case performance (if you pick the worst pivot each
// time) is O(n^2).  Conversely, mergeSort's worst-case performance
// is the same as its average-case performance:  both are O(n log n).

// This sort operates by choosing a pivot, then splitting the
// vector so that the elements less than or equal to the pivot
// are to the left of the pivot, and those greater than the
// pivot are to the right of the pivot.  Then the two portions
// to the left and right of the pivot are recursively sorted.

int getPivotIndex(intVectorByReference v,int lo,int hi)
{
 return lo;
}

int pivot(intVectorByReference v, int lo, int hi)
{
 int pivotIndex;
 // 1. get a pivot index and swap it to the first position
 pivotIndex = getPivotIndex(v,lo,hi);
 swap(v[pivotIndex],v[lo]);

 // 2. Swap elements as necessary so those less than or
 //    equal to the pivot are in the left portion, and
 //    those greater than the pivot are in the right portion
 //    of the vector.
 int loPointer = lo + 1; // lo is the pivot, and we don't count it
 int hiPointer = hi;

 while (loPointer < hiPointer)
 {
  if (v[loPointer] <= v[lo])
   loPointer++;
  else if (v[hiPointer] > v[lo])
   hiPointer--;
  else
   // Both left and right elements are on the wrong
   // side, so swap them and continue.
   swap(v[loPointer],v[hiPointer]);
 }

 // 3. Swap the pivot into the new location
 assert(loPointer == hiPointer);
 int newPivotIndex;
 if (v[loPointer] <= v[lo])
  newPivotIndex=loPointer;
 else
  newPivotIndex=loPointer-1;
 swap(v[newPivotIndex],v[lo]);
 return newPivotIndex;
}

void quickSort(intVectorByReference v,int lo, int hi)
{
 if (lo >= hi)
  return;

 int p = pivot(v,lo,hi);

 quickSort(v,lo,p-1);
 quickSort(v,p+1,hi);
}

void quickSort(intVectorByReference v)
{
 quickSort(v,0,v.length()-1);
}

//////////////////////////////////////////////////
/////  radixSort()
//////////////////////////////////////////////////

// This sort is O(n log RANGE), where RANGE is the range of
// the elements in the vector.  For example, here we are using
// elements from 0 to 999,999, so our range is 10^6, and this
// requires 6 iterations, thus this is O(6 * n), which in fact
// is O(n).

// Thus, for large enough n, this sort will be arbitrarily
// faster than either mergeSort or quickSort (and of course
// will completely bury insertionSort, selectionSort, and bubbleSort).

typedef apvector<intVector> intVectorVector;

void radixSort(intVectorByReference v)
{
 intVectorVector buckets(BASE);
 intVector bucketCount(BASE);
 int i, len, bucket, bucketSize;
 len = v.length();

 // Initialize buckets
 int defaultBucketSize = 10 + 2 * len / BASE;
 for (i=0;i<BASE;i++)
 {
  bucketCount[i] = 0;
  buckets[i].resize(defaultBucketSize);
 }

 // Iterate over each expt up to MAX_EXPT
 int divver, modder = 1;
 for (int expt=0; expt < MAX_EXPT; expt++)
 {
  modder *= BASE;
  divver = modder / BASE;
  // 1.  Place each element v[j] into the approprate bucket
  //     based on the expt'th digit in v[j]
  for (int j=0;j<len;j++)
  {
   bucket = (v[j] % modder) / divver;
   bucketSize = buckets[bucket].length();
   // add v[j] to this bucket now
   // first make sure there is room
   if (bucketCount[bucket] >= bucketSize)
    buckets[bucket].resize(2*bucketSize);
   buckets[bucket][bucketCount[bucket]] = v[j];
   (bucketCount[bucket])++;
  }

  // 2.  Copy the buckets, from bucket[0] to bucket[BASE-1],
  //     back into v.
  //     AND clear the buckets for the next iteration by
  //     resetting the bucket count to 0!
  int vIndex = 0;
  for (bucket = 0; bucket < BASE; bucket++)
  {
   for (i=0; i<bucketCount[bucket];i++)
    v[vIndex++] = buckets[bucket][i];
   bucketCount[bucket] = 0;
  }
 }
}

//////////////////////////////////////////////////
/////  verifySorted() and testSort()
//////////////////////////////////////////////////

void verifySorted(intVectorByReference v)
{
 int cursor;
 for (cursor=v.length()-1; cursor>0; cursor--)
  if (v[cursor] < v[cursor-1])
  {
   cout << "Uh oh -- vector not sorted at index "
     << cursor << endl;
   return;
  }
 cout << "Wahoo -- the vector is sorted!" << endl;
}

// Note:  IntroCS students are *not* responsible
// for any part of the following function.
void testSortFunction(char* name,void(*sortFn)(intVector&v),intVector& v)
{
    intVector v2;
 int time1,time2;
    v2 = v;
 cout << endl << "Starting " << name << ": ";
 cout.flush();
 time1 = time(NULL);
    sortFn(v2);
 time2 = time(NULL);
 verifySorted(v2);
 cout << "Sort took: " << (time2 - time1) << " seconds" << endl;
}

//////////////////////////////////////////////////
/////  main()
//////////////////////////////////////////////////

void main()
{
    intVector v;
    int vSize;
 bool useSlowSorts;

 useSlowSorts = true;
    while (true)
    {
        cout << "Enter size of vector (0 to toggle slow sorts, <0 to exit): ";
        cin >> vSize;
        if (vSize < 0)
            return;

  if (vSize == 0)
  {
   useSlowSorts = !useSlowSorts;
   if (!useSlowSorts)
    cout << "not ";
   cout << "using slow sorts." << endl << endl;
  }
  else
  {
   v.resize(vSize);
   loadVector(v);
   cout << endl << "------------------------------";
   if (useSlowSorts)
   {
    testSortFunction("insertionSort",insertionSort,v);
    testSortFunction("selectionSort",selectionSort,v);
    testSortFunction("bubbleSort",bubbleSort,v);
   }
   testSortFunction("mergeSort",mergeSort,v);
   testSortFunction("quickSort",quickSort,v);
   testSortFunction("radixSort",radixSort,v);
   cout << "------------------------------" << endl << endl;
  }
    }
}