Merge Sort

The merge sort works on the idea of merging two already sorted lists. If there existed two already sorted list, merging the two together into a single sorted list can be accomplished in O(n) time.

Merge algorithm:

The algorithm to do so works as follows:

• Have a way to "point" at the first element of each of the two list

• compare the values being pointed at and pick the smaller of the two

• copy the smaller to the merged list, and advance the "pointer" of just that list to the next item.

• Continue until one of the list is completely copied then copy over remainder of the rest of the list

Merge Sort Implementation

Now, the merge algorithm is an O(n) algorithm as we pick n items between two lists. However, it depends on having two lists that are already sorted...So we must first get a list into that state.

We also need a second array to store the merged list. Our mergeSort() function should also not look any different than any other sorting function (ie all you need for a sorting function is the array). The sorting algorithm creates a temporary array once and passes that into a recursive function to do all the work. The idea here is that we don't want to allocate memory on each merge... instead we can just use one array that stays around for the entire process.

template <class TYPE>
void mergeSort(vector<TYPE>& arr){
  vector<TYPE> tmp(arr.size());
  //call mergeSort with the array, the temporary
  //and the starting and ending indices of the array
  mergeSort(arr,tmp,0,arr.size()-1);
}

This algorithm is recursive in nature. The idea is that we have a function that if it works, will sort an array between start and end inclusive. So how it works is we start with the big array and we mergeSort() each of the two halves of it. We can then merge the two lists together. to form a sorted list.

The base case for this algorithm is when we have an array that is one element long (ie start and end are the same). A list that has one element is always sorted. So if we merged two of these lists that are one element big together, we will create a list that is 2 elements and sorted.

//this function sorts arr from index start to end
template <class TYPE>
void mergeSort(vector<TYPE>& arr, vector<TYPE>& tmp, int start, int end){
  if (start<end){
    int mid=(start+end)/2;
    mergeSort(arr,tmp,start,mid);
    mergeSort(arr,tmp,mid+1,end);
    merge(arr,tmp,start,mid+1,end);
  }
}

This merge function is the code as stated in the previous description

template <class TYPE>
void merge(vector<TYPE>& arr, vector<TYPE>& tmp, int start,
    int start2, int end){
    int aptr=start;
    int bptr=start2;
    int i=start;
    while(aptr<start2 && bptr <= end){
        if(arr[aptr]<arr[bptr])
            tmp[i++]=arr[aptr++];
        else
            tmp[i++]=arr[bptr++];
    }
    while(aptr<start2){
        tmp[i++]=arr[aptr++];
    }
    while(bptr<=end){
        tmp[i++]=arr[bptr++];
    }
    for(i=start;i<=end;i++){
        arr[i]=tmp[i];
    }
}