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!

user5056973
  • 387
  • 5
  • 16

2 Answers2

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.
Slazer
  • 4,750
  • 7
  • 33
  • 60
  • Thanks! It seems to work after changing k to = 0. Here's how I'm using the functions in main: vector v = { 4, 2, 5, 1, 7, 3 }; mergeSort(v, 0, 5); for (int i = 0; i < v.size(); i++) { out << v[i];} – user5056973 Oct 29 '15 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< – Slazer Oct 29 '15 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:)

Liyang Chen
  • 112
  • 7
  • 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 Oct 29 '15 at 06: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... – Liyang Chen Oct 29 '15 at 06:45
  • Thank you! I changed it to k=0 and it seems to run fine now. Here's a screenshot: http://prntscr.com/8wshjz. I'm not sure I understand the errors on the bottom right. – user5056973 Oct 29 '15 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](http://stackoverflow.com/questions/12954821/cannot-find-or-open-the-pdb-file-in-visual-studio-c-2010) and [Error Message : Cannot find or open the PDB file](http://stackoverflow.com/questions/15937707/error-message-cannot-find-or-open-the-pdb-file) :) – Liyang Chen Oct 29 '15 at 19:51