2

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!

2
  • 1
    What is the output? What is the expected output? Which area of code do you think is the mistake in? Commented Oct 29, 2015 at 5:48
  • 1
    Have you tried stepping through the code line by line in a debugger? Commented Oct 29, 2015 at 5:49

2 Answers 2

2

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.
2
  • Thanks! It seems to work after changing k to = 0. Here's how I'm using the functions in main: vector<int> v = { 4, 2, 5, 1, 7, 3 }; mergeSort(v, 0, 5); for (int i = 0; i < v.size(); i++) { out << v[i];} Commented Oct 29, 2015 at 19:38
  • Glad I helped. I noticed the mergeSort() definition just now. Have not seen it before. In that case only the 3rd problem might be relevant. Your use the function correctly. You can use the C++11 way to print an array. for (auto i:v) cout<<i;
    – Slazer
    Commented Oct 29, 2015 at 20:48
1

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:)

4
  • I compiled it and there is no error. No runtime error either (when used correctly). I think the mistake is not in the implementation that the OP provided (except the k=0 problem, as you have said) but in the incorrect usage of the function.
    – Slazer
    Commented Oct 29, 2015 at 6:39
  • @Slazer I agree with you... there may be problem in how the function is used. At least it would be more clear if OP can provide more information like how the function is used and what the input is like... Commented Oct 29, 2015 at 6:45
  • Thank you! I changed it to k=0 and it seems to run fine now. Here's a screenshot: prntscr.com/8wshjz. I'm not sure I understand the errors on the bottom right. Commented Oct 29, 2015 at 19:42
  • 1
    @user5056973 Great it works. PDB files help you to debug DLLs, and if you don't have them, you can't set breakpoint to step into the coresponding DLL. For details I think you can refer to some great explaination Cannot find or open the PDB file in Visual Studio C++ 2010 and Error Message : Cannot find or open the PDB file :) Commented Oct 29, 2015 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.