Thread: Merge Sort - Invalid Output ??

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    82

    Merge Sort - Invalid Output ??

    Code:
    #include <iostream>
    
    using namespace std;
    
    
    void mergeSort(int a[], int low, int high);
    void merge (int a[], int low1, int high1, int low2, int high2);
    
    int main()
       {
       int sort[10]={6, 5, 8, 2, 12, 21, 11, 15, 25, 32};
    
       mergeSort(sort,0,9);
    
       for(int i =0; i<10; i++)
          {
          cout << sort[i] << endl;
          }
    
       return 0;
       }
    
    void mergeSort(int a[], int low, int high)
       {
       if (low >=high) return;
       int mid = (low+high)/2;
    
       mergeSort(a, low, mid);
       mergeSort(a, mid+1, high);
       merge(a, low, mid, mid+1, high);
       }
    
    void merge(int a[], int low1, int high1, int low2, int high2)
       {
       int t, i1, i2;
       int *temp;
       i1 = low1;
       i2 = low2;
       t = 0;
    
      while (i1 <= high1 && i2 <= high2)
         {
         if (a[i1] < a[i2])
           temp[t++] = a[i1++] ;
    
         else
           temp[t++] = a[i2++] ;
         }
    
       while (i1 <= high1)
         temp[t++] = a[i1++] ;
    
       while (i2 <= high2)
         temp[t++] = a[i2++] ;
    
       for (t = low1; t <= high2; t++)
          {
          a[t] = temp[t - low1] ;
          }
    
       }
    Output I get is

    11
    11
    11
    11
    11
    11
    15
    21
    25
    32


  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > int *temp;
    Well this isn't pointing anywhere at the moment.

    Even if it did, it would still need to be copied back to the original array.

    I thought the merge was supposed to take place in the original array?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    Quote Originally Posted by Salem
    > int *temp;
    Well this isn't pointing anywhere at the moment.

    Even if it did, it would still need to be copied back to the original array.

    I thought the merge was supposed to take place in the original array?

    thanks I fixed it now it works

    int temp[10];

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I thought the merge was supposed to take place in the original array?
    Not if you want it to be reasonably efficient. An in-place merge is a pain to get right, and it's much slower than using O(N) extra space. That's why merge sort isn't such a good option for arrays, but kicks butt for linked lists. So for arrays you merge to the auxiliary array, then copy back to the original array and wonder why you didn't use quicksort.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. array sort output problem
    By radiantarchon28 in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2007, 01:49 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  3. Base converter libary
    By cdonlan in forum C++ Programming
    Replies: 22
    Last Post: 05-15-2005, 01:11 AM
  4. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  5. Natural Merge Sort
    By penny_731729 in forum C Programming
    Replies: 1
    Last Post: 04-28-2003, 04:12 PM