Mergesort implementatie

wander.c

#include "as1_t2.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

// CONFIGURATION.

// Change these to change the type of array msort sorts, or the key it sorts
// on.

typedef task_t elem;

inline unsigned long key(elem** el) {
	return (*el)->id;
}

// IMPLEMENTATION FUNCTIONS.

// Allocate and clear a bit of memory, failing hard if that doesn't work
void* xcalloc(size_t nmemb, size_t size) {
	void* mem = calloc(nmemb, size);

	if (mem == NULL) {
		char* msg = "FATAL: Memory exhausted (tried to allocate %d bytes)\n";
		fprintf(stderr, msg, nmemb * size);
		exit(EXIT_FAILURE);
		return NULL;
	} else {
		return mem;
	}
}

// Dump the list of elements in the list to standard output. Useful for
// debugging.
void msort_dump(elem** elems, int count) {
	printf("[");

	for (int i = 0; i < count; i++) {
		printf("%ld", key(elems + i));
		if (i + 1 < count) printf(", ");
	}

	printf("]\n");
}

// Merge the left and right sublists inside the [first, last) range of elems.
void msort_merge(elem** elems, int first, int last) {
	int count = last - first;
	int mid = first + (count/2);

	// Lay down some ground rules.
	assert(first >= 0);
	assert(last > first);
	assert(count >= 2);

	// Allocate a buffer to put the sorted result in.
	elem** buf = xcalloc(count, sizeof(elem*));

	// Pointers!
	elem** left = elems + first;
	elem** center = elems + mid;
	elem** right = elems + last;

	elem** a = left;
	elem** b = center;

	// While there are elements left to sort...
	for (int i = 0; i < count; i++) {
		if (a < center && b < right) {
			// We have elements both on the left and the right

			if (key(a) <= key(b)) {
				// A <= B, so put A in the buffer and advance A
				buf[i] = *(a++);
			} else {
				// B < A, so put B in the buffer and advance B
				buf[i] = *(b++);
			}
		} else if (a < center) {
			// Trailing elements on the left. Add them.
			buf[i] = *(a++);
		} else if (b < right) {
			// Trailing elements on the right. Add them.
			buf[i] = *(b++);
		} else {
			break;
		}
	}

	// Our buffer has been prepared, copy it over our input.
	memcpy(elems + first, buf, count * sizeof(elem*));

	// Don't need the buffer anymore.
	free(buf);

	return;
}

void msort_range(elem** elems, int start, int end) {
	// Sanity checking.
	assert(elems != NULL);
	assert(start >= 0);
	assert(end >= start);

	if (start == end) {
		// Empty list is already sorted
		return;
	} else if (end - start == 1) {
		// List with one element is already sorted
		return;
	} else {
		// Find out the index of the middle element
		int mid = start + ((end - start) / 2);

		// Call ourselves for our left side, our right side, then merge
		msort_range(elems, start, mid);
		msort_range(elems, mid, end);
		msort_merge(elems, start, end);
	}
}

void msort(elem** elems, int count){
	// Entry point for the merge sort. Sorts the whole list of elems
	// destructively.
	msort_range(elems, 0, count);
}

/* vim: set ts=4 sw=4 noet: */