Thread: help with merge sort

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    43

    help with merge sort

    Write a function to recursively and visually do a merge-sort of a
    given array of 20 numbers. Be sure that after each merge the entire contents of the array
    are printed to the screen, including the number of merges so far that the
    current array arrangement represents.

    An example run for 5 numbers would look like:

    Enter 5 integers: 5 0 1 4 3

    The interim results of the merge_sort algorithm are:

    INDEX: 0 1 2 3 4
    --------------------
    Merge # 1: 5 0 1 4 3
    Merge # 2: 0 5 1 4 3
    Merge # 3: 0 1 5 4 3
    Merge # 4: 0 1 5 3 4
    Merge # 5: 0 1 3 4 5

    I need it to run for 20 integers and i don't know how to begin. I know to use the merge sort algorithm but thats it.

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    You need to apply mergesort to the array, since you already know how to do that, you only need to implement it. So your recursive function could contain the recursion step, the end step and a print function to print the actual state of the array.

    Assuming you know the basics of C programming I would suggest to design the program, implement it and then test it. If it doesn't work try to find the error and if there are still questions after a while, post your code and question.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    43
    This is what i have so far:

    #include <stdio.h>
    #include <stdlib.h>

    #define MAX 200

    int factorial(int n);
    void input();
    void merge_sort(int sort[], int first, int last);
    void move(int list1[], int first1, int last1, int list2[], int first2);
    void merge(int list[], int first1, int last1,
    int first2, int last2);
    int main(void)
    {
    some code
    return 0;
    }
    void merge_sort(int sort[], int first, int last)
    {

    if(first < last) {
    merge_sort( sort, first, (first+last)/2);
    merge_sort( sort, (first+last)/2 + 1, last);
    merge(sort, first, (first+last)/2, (first+last)/2 + 1, last);
    }
    }
    void merge(int lists[], int first1, int last1,
    int first2, int last2)
    {
    int temp[MAX];
    int index, index1, index2;
    int num;


    index = 0;
    index1 = first1;
    index2 = first2;
    num = last1 - first1 + last2 - first2 + 2;

    /* while there are still elements in both lists,
    * put the smallest element in the temporary array.
    */

    while((index1 <= last1) && (index2 <= last2)) {
    if(lists[index++] < lists[index2])
    temp[index++] = lists[index1++];
    else
    temp[index++] = lists[index2++];
    }

    /* after one list is empty, fill the temporary array
    * with the remaining elements in the other list.
    */


    if(index1 > last1)
    move(lists, index2, last2, temp, index);
    else
    move(lists, index1, last1, temp, index);

    /* copy the list to original array */
    move(temp, 0, num-1,lists, first1);
    }
    void move(int list1[], int first1, int last1, int list2[], int first2)
    {
    while(first1 <= last1)
    list2[first2++] = list1[first1++];
    }

    I get segmentation fault what is wrong?

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    43
    Any suggestions?

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    43
    help

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort the best sorting algorithm?
    By sehr alt in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 06-20-2007, 02:19 PM
  2. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  3. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 11:14 AM
  4. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  5. merge sort tutorial from cprogramming.com
    By Micko in forum C Programming
    Replies: 0
    Last Post: 03-15-2005, 09:43 AM