M-ary heapsort

m_ary-heapsort.c

/*
	This started from coding ternary heapsort while on my lunch break.
	It then occured to me that the heapify algorithm could be easily
	extended to any m-ary heap (except of course, a 1-ary heap(list?))
	as shown heapify creates a pentary-heap. changing the #define MARY value
	will set the branching value of the heap.
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MARY 5 //2 = binary heap, 3 = ternary heap, etc. etc. etc.
void exch(int a[], int l, int r)
{
	int t = a[l];
	a[l] = a[r];
	a[r] = t;
}


void maryheapify(int a[], int n, int m, int k)
{
	int largest = k;
	for (int i = 0; i < m; i++)
	{
		int pos = 2*k + i;
		if (pos < n && a[pos] > a[largest])
			largest = pos;
	}
	if (largest != k) {
		exch(a, largest, k);
		maryheapify(a, n, m, largest);
	}
}

void maryheapsort(int a[], int n) {
	for (int i = n/2; i  >= 0; i--)
		maryheapify(a, n, MARY, i);
	for (int i = n - 1; i > 0; i--) {
		exch(a, i, 0);
		maryheapify(a, i, MARY, 0);
	}
}

_Bool checksort(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		if (a[i+1] < a[i])
			return false;
	}
	return true;
}

void printArr(int a[], int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	puts(" ");
}

int main()
{
	int n = 25;
	int *to_sort = (int*)malloc(sizeof(int)*n);
	for (int i = 0; i < n; i++) {
		to_sort[i] = rand() % 100;
	}
	printArr(to_sort, n);
	maryheapsort(to_sort, n);
	printArr(to_sort, n);
	if (checksort(to_sort, n)) puts("Heapsort Successful.");
	else puts("This weird sort doesnt even work.");
	return 0;
}