I came across this source code lying in the kernel SRC, about a NON recursive sorting algorithm which does a pretty decent job at worst and average case scenarios.
The source file is /lib/sort.c
Prototype:void sort(void *base, size_t num, size_t size, int (*cmp_func)(const void *, const void *), void (*swap_func)(void *, void *, int size))
This function does a heapsort on the given array. You may provide a
* swap_func function optimized to your element type.
* Sorting time is O(n log n) both on average and worst-case. While qsort is about 20% faster on average, it suffers from exploitable O(n*n) worst-case behavior and extra memory requirements that make it less suitable for kernel use.
Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.
So our 1st task is to understand the HEAP DS.
A heap is a kind of binary tree having this property: every parent value is greater than (or equal to) its children's.
The root always holds the max value
If the Parent value is less than its children, then the value is sifted down repeatedly until it proper heap is formed.
Suppose we have the following, arbitrarily assigned, array:
The right half side (the blue marked side) is already arranged as
the bottom row of a heap, because its items have no children:
consider, for instance the first 'blue' item, having value 24.
Its index is 7, hence the heap properties for such item
(h7>= h15, h7>= h16) are automatically satisfied, because there are no items with index 15 or 16 in the array.
So the 'blue side' is our partial heap and we can proceed with heap construction by repeatedly sifting down the items of the 'red side'.
3 - sifting down the first 'red' (left side) item of the array
The sift function would be implemented like this:
void sift(int a[], int size, int l)
{
int i,j, x;
i = l;
j = 2*i+1;
x = a[i];
while (j < size)
{
if ( j <size - 1)
if ( a[j] < a[j+1])
++j;
if (x >= a[j])
break;
a[i] = a[j];
i = j;
j = 2*i + 1; }
a[i] = x;
}
The creation of heap than becomes like this:
void make_heap(int a[], int size)
{
int l = size / 2;
while (l)
{
--l;
sift(a, size, l);
}
}
After all the operations are finished, We will get a heap array with
First element in array as Maximum value element in the unsorted
array.
The 1st Fig: Unsorted Array. Fig2: Heaped array---> (29 is the max value).
so that the maximum value (29) is now the first item of the array (or, in other words, is on the top of the heap).
We can remove such maximum value (storing it in a safe place) and rearrange the remaining items in order to regain a heap (to obtain another 'maximum', that is the successive value of the sorted sequence).
It turns out the safe place for storing the maximum value is the last item of
the array. As matter of fact, we swap the first and last item.
Now we have:
The maximum value in its own safe place (grayed, on the right side of the array)
A partial heap to fix (the blue items)
An item to sift down (the read one)
So We implement this heap_sort for arranging in descending order is:
void heapsort(int a[], int size)
{
int l = 0, r = size;
make_heap(a, size);
while ( r > 1)
{
int tmp = a[0];
--r;
a[0] = a[r];
a[r] = tmp;
sift(a, r,0);
}
}
NOTE: All credit for the diagrams and Source code for Heap sort goes to this guy:http://www.codeproject.com/Tips/732196/Heap-Data-Structure-and-Heap-Sort
Now coming back to our kernel code for sort.c
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2 - 1) * size, n = num * size, c, r;
if (!swap_func) {
if (size == 4 && alignment_ok(base, 4))
swap_func = u32_swap;
else if (size == 8 && alignment_ok(base, 8))
swap_func = u64_swap;
else
swap_func = generic_swap;
}
/* heapify */
for ( ; i >= 0; i -= size) {
for (r = i; r * 2 + size < n; r = c) {
c = r * 2 + size;
if (c < n - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
/* sort */
for (i = n - size; i > 0; i -= size) {
swap_func(base, base + i, size);
for (r = 0; r * 2 + size < i; r = c) {
c = r * 2 + size;
if (c < i - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
}
