Thread: Mergesort in C

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    2

    Mergesort in C

    Hello,

    For an assignment I have to sort a large amount of numbers with multithreading in C. I am new to C however the part with the threading is going fine. There is some problem with my MergeSort algorithm though, and after staring at it for hours I still can't figure out what the problem is. Maybe someone with a fresh mind..?

    Mergesort repeatedly devises an array into two parts, a left and a right part. These parts are sorted recursively and then combined into the resulting array.
    (the array is split until the length of one part equals 1, because then left=right and it is trivially sorted)

    Code:
    void mergesort(int array_to_sort[], int left, int right)
    {
        int splitpos;
    
        if (left < right)
        {
            // Partition the array into two subarrays, sort these subarrays recursively and then merge them into
            // a correctly sorted array.
            splitpos = (left + right) / 2;
            mergesort(array_to_sort, left, splitpos);
            mergesort(array_to_sort, splitpos + 1, right);
            merge(array_to_sort, left, splitpos, right);
            }
    }
    Now the tricky bit, merging two sorted arrays into the resulting array. Determine sizes of both the first part and the second part of the array. Make auxiliary arrays to temporarely store these parts. Then, walk through both arrays with indices i and j, continuously adding the smallest number of either array. Eventually both arrays have been merged into one.
    Code:
    void merge(int array_to_sort[], int left, int splitpos, int right)
    {
        int size_array1 = splitpos - left + 1;
        int size_array2 = right - splitpos;
        int array1[size_array1];
        int array2[size_array2];
        int i = 0;
        int j = 0;
    
        // Copy both sub-arrays to auxilary arrays.
    
        for (i = 0; i < size_array1; i++)
        {
            array1[i] = array_to_sort[left + i];
            }
    
            for (j = 0; j < size_array2; j++)
            {
            array2[j] = array_to_sort[splitpos + j + 1];
            }
    
            i = 0;
            j = 0;
    
    
            int k;
    
            for (k = left; k <= right; k ++)
            {
                if ( j = size_array2 )
                { 
                array_to_sort[k] = array1[i];
                i++; 
                }
                else if ( i = size_array1 )
                {
                array_to_sort[k] = array2[j];
                j++; 
                }
                else if (array1[i] <= array2[j])
                {
                array_to_sort[k] = array1[i];
                i++;
                }
                else
                {
                array_to_sort[k] = array2[j];
                j++;
                }
        }
    }
    The problem is, I get an array with values like -12898313 after sorting an array with integers between 1 and 99. There must be a stupid mistake, but right now, I can't find it. Can you?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    One probable problem is that you are using assignment where you may want equality comparison, e.g., you use if ( j = size_array2 ) instead of if ( j == size_array2 ).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    2
    Thank you. i'm used to pascal, and when you stare at a screen for 5 hours you don't see stuff like that

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 12:12 PM
  2. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  3. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  4. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM
  5. MergeSort implementation with linklist.
    By Kam in forum C Programming
    Replies: 3
    Last Post: 10-21-2002, 11:04 AM

Tags for this Thread