Mergesort (internal)

mergesort.c

#include <stdio.h>
#include <stdlib.h>
 
#define LEN 20
#define MAXEL 100
 
void merge(int * list, int left_start, int left_end, int right_start, int right_end)
{
	int left_length = left_end - left_start;
	int right_length = right_end - right_start;
 
	int left_half[left_length];
	int right_half[right_length];
 
	int r = 0; 
	int l = 0; 
	int i = 0; 
 
	for (i = left_start; i < left_end; i++, l++)
	{
		left_half[l] = list[i];
	}

	for (i = right_start; i < right_end; i++, r++)
	{
		right_half[r] = list[i];
	}

	for ( i = left_start, r = 0, l = 0; l < left_length && r < right_length; i++)
	{
		if ( left_half[l] < right_half[r] ) { list[i] = left_half[l++]; }
		else { list[i] = right_half[r++]; }
	}

	for ( ; l < left_length; i++, l++) { list[i] = left_half[l]; }
	for ( ; r < right_length; i++, r++) { list[i] = right_half[r]; }
}
 
void mergesort_r(int left, int right, int * list)
{
	if (right - left <= 1)
	{
		return;
	}

	int left_start  = left;
	int left_end    = (left+right)/2;
	int right_start = left_end;
	int right_end   = right;

	mergesort_r( left_start, left_end, list);
	mergesort_r( right_start, right_end, list);
	merge(list, left_start, left_end, right_start, right_end);
}
 
void mergesort(int * list, int length)
{
	mergesort_r(0, length, list);
}
 
void print_list(int * list, int len)
{
	int i;
 
	printf("[ ");
	for (i = 0; i < len; i++)
	{
		printf("%d ", list[i]);
	}
	printf("]\n");
}
 
int main()
{
	int list[LEN], i;
	for (i = 0; i < LEN; i++) { list[i] = rand() % MAXEL; }
 
	printf("Antes do sort: ");
	print_list(list, LEN);
 
	mergesort(list, LEN);
 
	printf("Depois do sort: ");
	print_list(list, LEN);
 
	return 0;
}