Thread: 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;
}

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.

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.