// SPDX-License-Identifier: GPL-2.0
//
//  This is a modification of the 
//  original LINUX kernel heap sort function
//  The original did not have any license marking
//  but it is assumed it the license is GPL
//
//  Optimized heap sort used to sort a vector of long integers
//
//  Macros are used both to swap and compare to avoid 
//  any function call
//
#include    <stdlib.h>
#include    <stdio.h>

#define     swap(a, b, t)       do  {                       \
	                                (t) = *(a);             \
	                                *(a) = *(b);            \
	                                *(b) = t;               \
                                }   while(0);

#define     cmp_func(a, b)      (*(a) - *(b))

void optsortlong(long *vector, size_t length) {

	int         i;
    int         c;
    int         r;

    long        t;

    //
    //  Create the heap
    //
	for (i = length/2 - 1; i >= 0; i--) {
		for (r = i; r * 2 + 1 < length; r = c) {
			c = r * 2 + 1;
			if (c < length - 1 && cmp_func(vector + c, vector + c + 1) < 0)
				c++;
			if (cmp_func(vector + r, vector + c) >= 0)
				break;
			swap(vector + r, vector + c, t);
		}
	}

	//
    //  Sort the heap
    //
	for (i = length - 1; i > 0; i -= 1) {
		swap(vector, vector + i, t);
		for (r = 0; r * 2 + 1 < i; r = c) {
			c = r * 2 + 1;
			if (c < i - 1 && cmp_func(vector + c, vector + c + 1) < 0)
				c++;
			if (cmp_func(vector + r, vector + c) >= 0)
				break;
			swap(vector + r, vector + c, t);
		}
	}
}