Mergesort

This is a discussion on Mergesort within the C Programming forums, part of the General Programming Boards category; I am writing a program that sorts an array of randomized integers. Right now I am testing the program to ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    28

    Question Mergesort

    I am writing a program that sorts an array of randomized integers. Right now I am testing the program to see if it sorts or not. I am working up to seeing how long it takes my system to run the algorithm that sorts the array. But when I run the program to test if the algorithm is right, it crashes my cmd window. The cause eludes me. What's wrong with it?

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define N 100
    #define key(A) (A)
    #define less(A, B) (key(A) < key(B))
    int aux[N];
    
    void merge(int a[], int l, int m, int r) {
    	int i, j, k;
    	for(i=m+1; i>l; i--) aux[i-1] = a[i-1];
    	for(j=m; j<r; j++) aux[r+m-j] = a[j+1];
    	for(k = l; k <= r; k++)
    		if(less(aux[j], aux[i]))
    			a[k] = aux[j--]; 
    		else	
    			a[k] = aux[i++];
    }
    
    
    void mergesort(int a[], int l, int r) {
    	int m = (r+1)/2;
    	if(r <= l) return;
    	mergesort(a, l, m);
    	mergesort(a, m+1, r);
    	merge(a, l, m, r);
    }
    
    void random_array(int a[]) {
    	int i;
    	for(i=0; i<N; i++)
    		a[i] = rand();
    }
    
    int main() {
    	int a[N], i;
    
    
    	srand((unsigned) time(NULL));
    
    	random_array(a);
    	mergesort(a, 0, N-1);
    	
    
    	for(i=0;i<15;i++)
    		printf("%d\n", a[i]);
    	printf("\n");
    
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    May 2004
    Posts
    127
    I see I got here too late. In your other thread I warned you about Robert Sedgewick's code, and this is a prime example. Keep a close watch on the variables being used, it's surprisingly easy to mistake l (letter ell) for 1 (number one). You do just that here.
    Code:
    void mergesort(int a[], int l, int r) {
    	int m = (r+1)/2;
    	if(r <= l) return;
    	mergesort(a, l, m);
    	mergesort(a, m+1, r);
    	merge(a, l, m, r);
    }
    The calculation for m should be (r+l)/2. The reason you were crashing is because of a stack overflow. The recursion went too deep.

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    28
    Thank you thank you. My teacher told my class to use the code from Sedgewick's book to sort the array...but I've been having some problems with his quicksort and mergesort algorithms, as well as his BST rotation algorithm. You're a life saver.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21