CODEWITHSUNDEEP
c++arrayssortingmergesort
coopwatts
coopwatts

Reputation: 690

Funky Results when running implementation of Merge Sort

I am trying to implement Merge sort for time analysis and when testing the functions used to implement this, I get some funky results and can't figure out why. I am generating an array of 20 random values, then calling mergeSortand then printing the results of the "sorted" array.

There is no error message, but the results are not what's expected. The output will appear to be sorted for the first few values, then some 0's in between, and eventually ending in very very large values, even though the numbers being generated should be between 1 and 100. The output is as follows:

>sort-timings
1 3 8 11 0 14 17 24 0 0 29 96 20 2293400 3 2293400 2293400 26085452 1971496002 1971496002 >Exit code: 0    Time: 0.4162

The code I have implemented is: 

void merge(int A[], int leftStart, int leftEnd, int rightStart, int rightEnd, int W[]) {
   //Merge A[leftStart]....[leftEnd] with A[rightStart]...[rightEnd]
   //Into W, indexed by k, copy resulting W into A
   int i = leftStart;
   int j = rightStart;
   int k = leftStart;
   while( i <= leftEnd && j <= rightEnd) {
      if(A[i] < A[j]) {
         W[k++] = A[i++];
      }
      else if(A[i] > A[j]) {
         W[k++] = A[j++];
      }
      else {
         W[k++] = A[i++];
         W[k++] = A[j++];
      }
   }
   for(i = leftStart; i <= rightEnd; i++) {
      A[i] = W[i];
   }
}

void mergeSort(int A[], int low, int high, int W[]) {
   //mergeSort Helper Function
   if(low == high) {
      return; //1 element is sorted
   }
   int mid = (low + high) / 2;
   mergeSort(A, low, mid, W); //Sort first half
   mergeSort(A, mid + 1, high, W); //Sort second half
   merge(A, low, mid, mid + 1, high, W);
   return;
}

void mergeSort(int A[], int W[], int n) {
   mergeSort(A, 0, n - 1, W);
}

void generateRandomArray(int A[], int n) {
   unsigned int seed = time(0);
   srand(seed);
   for(int i = 0; i < n; i++) {
      A[i] = (rand() % 100) + 1; // 1 <= A[i] <=10000
   }
}

int main() {
   const int ARRAY_SIZE = 20;
   int array[ARRAY_SIZE];
   int tempArray[ARRAY_SIZE];
   generateRandomArray(array, ARRAY_SIZE);
   mergeSort(array, tempArray, ARRAY_SIZE);   
   for(int i = 0; i < ARRAY_SIZE; i++) {
      cout << array[i] << " ";
   }
}

Upvotes: 0

Views: 77

Answers (2)

rcgldr
rcgldr

Reputation: 28828

Alternate version that uses a flag (mtoa) to keep track of which direction to merge based on the level of recursion, to avoid copying of data. It also only checks for index out of range after incrementing an index in TopDownMerge(); I'm not sure if this make a significant performance difference.

void TopDownMergeSort(int a[], int b[], size_t n)
{
    if(n < 2)
        return;
    TopDownSplitMerge(a, b, 0, n, true);
}

void TopDownSplitMerge(int a[], int b[], size_t ll, size_t ee, bool mtoa)
{
size_t rr;
    if ((ee - ll) == 1){                    // if size == 1
        if(!mtoa)                           //  copy to b if merging a to b
            b[ll] = a[ll];
        return;
    }
    rr = (ll + ee)>>1;                      // midpoint, start of right half
    TopDownSplitMerge(a, b, ll, rr, !mtoa);
    TopDownSplitMerge(a, b, rr, ee, !mtoa);
    if(mtoa)                                // if merging to a, merge b to a
        TopDownMerge(b, a, ll, rr, ee);
    else                                    // else merge a to b
        TopDownMerge(a, b, ll, rr, ee);
}

void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                          // b[]       index
    size_t l = ll;                          // a[] left  index
    size_t r = rr;                          // a[] right index
    while(1){                               // merge data
        if(a[l] <= a[r]){                   // if a[l] <= a[r]
            b[o++] = a[l++];                //   copy a[l]
            if(l < rr)                      //   if not end of left run
                continue;                   //     continue (back to while)
            while(r < ee){                  //   else copy rest of right run
                b[o++] = a[r++];
            }
            break;                          //     and return
        } else {                            // else a[l] > a[r]
            b[o++] = a[r++];                //   copy a[r]
            if(r < ee)                      //   if not end of right run
                continue;                   //     continue (back to while)
            while(l < rr){                  //   else copy rest of left run
                b[o++] = a[l++];
            }
            break;                          //     and return
        }
    }
}

Upvotes: 1

The Dark
The Dark

Reputation: 8514

You are stopping your merge loop to early. It currently stops when i is out of range or j is out of range, this leaves some values not copied into W, leading to uninitialized values in your output.

A simple way to fix this, is to copy the rest of the values after your main loop is finished. If the loop finished because i was out of range, you want to copy the rest of j, similarly if the loop finished because j was out of range, you want to copy the rest of i.

You can achieve this by adding loops after the main loop to ensure both i and j reach the end of their range:

while (i <= leftEnd) {
    W[k++] = A[i++];
}
while (j <= rightEnd) {
    W[k++] = A[j++];
}

put this before the final for loop that copies W into A.

Another alternative is to change the loop so that the condition is an || which will mean it will continue while either number is in range. You then have to test that a number is in range before you use it. There are a number of ways to do this, one simple way is to test it first:

while (i <= leftEnd || j <= rightEnd) {
    if (j > rightEnd) {
        W[k++] = A[i++];
    }
    else if (i > leftEnd) {
        W[k++] = A[j++];
    }
    else if (A[i] < A[j]) {
    ...

Upvotes: 1

Related Questions