Merge Sort Using Vectors (int) C++

Question

I can't seem to figure out what's wrong with my code. As the title says, I am trying to implement merge sort using integer vectors.

HEADER:

using Val = int;
using Container = std::vector<Val>;
using Iter = long;
void mergeSort(Container& arr, Iter start, Iter end);

.CPP (I've included the definition of merge in the file, just not pictured here)

void mergeSort(Container& arr, Iter start, Iter end) {

if (start >= end) return;

int mid = (start + end) / 2;

mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, end, mid);


}

void merge(Container& arr, Iter start, Iter end, Iter mid)
{

int len = end - start + 1;
int x = 0;
Container temp;

temp.resize(arr.size());

int i, j, k;
i = start;
k = start;
j = mid + 1;

while (i <= mid && j <= end)
{
    if (arr[i] < arr[j])
    {
        temp[k++] = arr[i++];
    }
    else
    {
        temp[k++] = arr[j++];
    }
}



while (i <= mid) temp[k++] = arr[i++];


while (j <= end) temp[k++] = arr[j++];

for (k = 0; k < len; k++) arr[k + start] = temp[k];

}

many thanks!

Answer 1

I think there might be four problems with your code.

1. You assume the sequence <start,mid> and <mid+1,end> is sorted. If this condition does not hold (e.g. merge(v,0,3,2) on {6,5,7,4}) the algorithm will give incorrect results.
2. You use incorrect end value when using a function (e.g. merge(v,0,4,2) on the array {6,5,7,4}. You always have to iterate over <0,size-1>.
3. As already said k should be always initialized to 0. You want to insert the sorted sequence to the beginning of the sorted array.
4. You assume that the argument mid is the index, not position of the element in the array. For example merge(v,0,3,2) would yield incorrect result on {1,6,2,4}, because in the function you sort the sequence from index mid+1=2+1=3 to 3, which contains only {4}. Therefore, your first part {1,6,2} is not sorted, which is required by your algorithm.

The solution is to:

1. Initialize k to 0.
2. Check if mid<end.
3. Sort <0,mid> and <mid+1,end> using another sorting algorithm.