CODEWITHSUNDEEP
c++vectorintmergesort
user5056973
user5056973

Reputation: 447

Merge Sort Using Vectors (int) C++

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!

Upvotes: 2

Views: 2152

Answers (2)

Slazer
Slazer

Reputation: 4990

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.

Upvotes: 2

Liyang Chen
Liyang Chen

Reputation: 122

Only looking at your code, one problem I think is the initial value of k in the merge function.

If you put the temp value in the Container temp starting from position 0, then you should initialize k to 0

k = 0;

Or if you want the position starting from start, then you would need to change the last for loop to

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

However, please post more information about the problem you encounter.. is it a Compilation Error? or a Runtime Error? or the result doesn't match your expectation? In addition, show what have you done to solve the problem:)

Upvotes: 1

Related Questions