Blog Entry © Thursday, January 23, 2025, by James Pate Williams, Jr. Merge Sort Verus Quick Sort

// MergeVersusQuick.c : This file contains the 'main' function.
// Program execution begins and ends there.
// mergesort is from "A Numerical Library in C for Scientists
// and Engineers" by H. T. Lau Translated from ALGOL NUMAL
// QuickSort is from "Introduction to Algorithms" by Thomas H.
// Cormen, Charles E. Leiserson, and Ronald L. Rivest

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

#define LENGTH1			17		// static side-by-side test
#define LENGTHM1		16		// upper index
#define LENGTH2		  4097		// time test array length
#define LENGTHM2      4096		// upper inndex
#define NUMBER_TESTS  4096		// number of timing tests

void mergesort(float a[], int p[], int low, int up)
{
	int* allocate_integer_vector(int, int);
	void free_integer_vector(int*, int);
	void merge(int, int, int, int[], float[], int[]);
	int i, lo, step, stap, umlp1, umsp1, rest, restv, * hp;

	hp = allocate_integer_vector(low, up);
	for (i = low; i <= up; i++) p[i] = i;
	restv = 0;
	umlp1 = up - low + 1;
	step = 1;
	do {
		stap = 2 * step;
		umsp1 = up - stap + 1;
		for (lo = low; lo <= umsp1; lo += stap)
			merge(lo, step, step, p, a, hp);
		rest = up - lo + 1;
		if (rest > restv && restv > 0)
			merge(lo, rest - restv, restv, p, a, hp);
		restv = rest;
		step *= 2;
	} while (step < umlp1);
	free_integer_vector(hp, low);
}

int* allocate_integer_vector(int l, int u)
{
	/*  Allocates an integer vector of range [l..u].  */

	void system_error(char*);
	int* p;

	p = (int*)malloc((unsigned)(u - l + 1) * sizeof(int));
	if (!p) system_error("Failure in allocate_integer_vector().");
	return p - l;
}

void free_integer_vector(int* v, int l)
{
	/*  Frees an integer vector of range [l..u].  */

	free((char*)(v + l));
}

void system_error(char error_message[])
{
	void exit(int);

	printf("%s", error_message);
	exit(1);
}

void merge(int lo, int ls, int rs, int p[], float a[], int hp[])
{
	/* this procedure is used internally by MERGESORT */

	int l, r, lout, rout, i, pl, pr;

	l = lo;
	r = lo + ls;
	lout = rout = 0;
	i = lo;
	do {
		pl = p[l];
		pr = p[r];
		if (a[pl] > a[pr]) {
			hp[i] = pr;
			r++;
			rout = (r == lo + ls + rs);
		}
		else {
			hp[i] = pl;
			l++;
			lout = (l == lo + ls);
		}
		i++;
	} while (!(lout || rout));
	if (rout) {
		for (i = lo + ls - 1; i >= l; i--) p[i + rs] = p[i];
		r = l + rs;
	}
	for (i = r - 1; i >= lo; i--) p[i] = hp[i];
}

int Partition(float a[], int lo, int hi)
{
	int pivotIndex = lo + (hi - lo) / 2;
	float x = a[pivotIndex];
	float t = x;

	a[pivotIndex] = a[hi];
	a[hi] = t;

	int storeIndex = lo;

	for (int i = lo; i < hi; i++)
	{
		if (a[i] < x)
		{
			t = a[i];
			a[i] = a[storeIndex];
			a[storeIndex++] = t;
		}
	}

	t = a[storeIndex];
	a[storeIndex] = a[hi];
	a[hi] = t;

	return storeIndex;
}

void DoQuickSort(float a[], int n, int p, int r)
{
	if (p < r)
	{
		int q = Partition(a, p, r);

		DoQuickSort(a, n, p, q - 1);
		DoQuickSort(a, n, q + 1, r);
	}
}

void QuickSort(float a[], int n)
{
	DoQuickSort(a, n, 1, n);
}

double runtime[2][NUMBER_TESTS];
float A[LENGTH1] = { 0 }, a[LENGTH1] = { 0 };
float AA[LENGTH2] = { 0 }, aa[LENGTH2] = { 0 };
float b[LENGTH1] = { 0 };
int n = NUMBER_TESTS;
int pp[LENGTH2];

int main()
{
	while (1)
	{
		float x;
		int i, j, option = 0, p[LENGTH1], seed = 1;

		printf("== Menu ==\n");
		printf("1 Side-by-Side Tests\n");
		printf("2 Timing Comparisons\n");
		printf("3 Exit\n");
		printf("Enter an option: ");
		scanf_s("%d", &option);

		if (option == 3)
			break;

		if (option == 1 || option == 2)
		{
			printf("Enter a PRNG Seed >= 1: ");
			scanf_s("%u", &seed);
			srand(seed);

			if (option == 1)
			{
				for (i = 1; i <= LENGTHM1; i++)
				{
					x = (float)rand() / RAND_MAX;
					A[i] = x;
					a[i] = x;
					b[i] = x;
				}

				mergesort(A, p, 1, LENGTHM1);
				QuickSort(a, LENGTHM1);

				for (i = 1; i <= LENGTHM1; i++)
					printf("%f\t%f\t%f\n", b[i], A[p[i]], a[i]);
			}

			else if (option == 2)
			{
				double mean[2] = { 0 }, median[2] = { 0 }, stdDev[2] = { 0 };
				double Sx[2] = { 0 };
				
				for (j = 0; j < n; j++)
				{
					for (i = 1; i <= LENGTHM2; i++)
					{
						x = (float)rand() / RAND_MAX;
						AA[i] = x;
						aa[i] = x;
					}
					
					clock_t start1 = clock();
					mergesort(AA, pp, 1, LENGTHM2);
					clock_t finis1 = clock();
					clock_t start2 = clock();
					QuickSort(aa, LENGTHM2);
					clock_t finis2 = clock();
					runtime[0][j] = ((double)finis1 - start1) / 
						CLOCKS_PER_SEC;
					runtime[1][j] = ((double)finis2 - start2) / 
						CLOCKS_PER_SEC;
					mean[0] += runtime[0][j];
					mean[1] += runtime[1][j];
				}

				for (j = 0; j < n; j++)
				{
					Sx[0] = pow((double)runtime[0][j] - mean[0], 2.0) / ((double)n - 1);
					Sx[1] = pow((double)runtime[1][j] - mean[1], 2.0) / ((double)n - 1);
				}

				stdDev[0] = (float)sqrt(Sx[0]);
				stdDev[1] = (float)sqrt(Sx[1]);

				printf("merge sort mean runtime (ms) = %3.0lf\n", 1.0e6 * mean[0] / n);
				printf("quick sort mean runtime (ms) = %3.0lf\n", 1.0e6 * mean[1] / n);
				printf("merge sort std dev (s) = %f\n", stdDev[0]);
				printf("quick sort std dev (s) = %f\n", stdDev[1]);
			}
		}
	}

	return 0;
}