1/* Sort.c */
2
3#include "Sort.h"
4
5#define HeapSortDown(p, k, size, temp) \
6  { for (;;) { \
7    UInt32 s = (k << 1); \
8    if (s > size) break; \
9    if (s < size && p[s + 1] > p[s]) s++; \
10    if (temp >= p[s]) break; \
11    p[k] = p[s]; k = s; \
12  } p[k] = temp; }
13
14void HeapSort(UInt32 *p, UInt32 size)
15{
16  if (size <= 1)
17    return;
18  p--;
19  {
20    UInt32 i = size / 2;
21    do
22    {
23      UInt32 temp = p[i];
24      UInt32 k = i;
25      HeapSortDown(p, k, size, temp)
26    }
27    while(--i != 0);
28  }
29  /*
30  do
31  {
32    UInt32 k = 1;
33    UInt32 temp = p[size];
34    p[size--] = p[1];
35    HeapSortDown(p, k, size, temp)
36  }
37  while (size > 1);
38  */
39  while (size > 3)
40  {
41    UInt32 temp = p[size];
42    UInt32 k = (p[3] > p[2]) ? 3 : 2;
43    p[size--] = p[1];
44    p[1] = p[k];
45    HeapSortDown(p, k, size, temp)
46  }
47  {
48    UInt32 temp = p[size];
49    p[size] = p[1];
50    if (size > 2 && p[2] < temp)
51    {
52      p[1] = p[2];
53      p[2] = temp;
54    }
55    else
56      p[1] = temp;
57  }
58}
59
60/*
61#define HeapSortRefDown(p, vals, n, size, temp) \
62  { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
63    UInt32 s = (k << 1); \
64    if (s > size) break; \
65    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
66    if (val >= vals[p[s]]) break; \
67    p[k] = p[s]; k = s; \
68  } p[k] = temp; }
69
70void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
71{
72  if (size <= 1)
73    return;
74  p--;
75  {
76    UInt32 i = size / 2;
77    do
78    {
79      UInt32 temp = p[i];
80      HeapSortRefDown(p, vals, i, size, temp);
81    }
82    while(--i != 0);
83  }
84  do
85  {
86    UInt32 temp = p[size];
87    p[size--] = p[1];
88    HeapSortRefDown(p, vals, 1, size, temp);
89  }
90  while (size > 1);
91}
92*/