Basic heapsort

hs.c

#include <stdio.h>
#include <stdlib.h>

void sift_down(int *a, int n, int j) {
  int j_rgt, val = a[j];
  while ((j_rgt = 2 * j + 2) <= n) {
    int j_lft = j_rgt - 1;
    if (j_rgt == n || a[j_lft] > a[j_rgt]) {
      if (val >= a[j_lft]) break;
      a[j] = a[j_lft];
      j = j_lft;
    } else {
      if (val >= a[j_rgt]) break;
      a[j] = a[j_rgt];
      j = j_rgt;
    }
  }
  a[j] = val;
}

void sort(int *a, int n) {
  for (int j = n / 2 - 1; j >= 0; --j) sift_down(a, n, j);
  for (int j = n - 1; j > 0; --j) {
    int t = a[0]; a[0] = a[j]; a[j] = t;
    sift_down(a, j, 0);
  }
}

int main(void) {
  int n = 1000000, a[n];
  for (int i = 0; i < n; ++i) a[i] = rand();
  sort(a, n);
  for (int i = 0; i < 100; ++i) printf("%d\n", a[i]);
  return 0;
}


// Alternate sift down that avoids some comparisons.
void sift_down_optimized(int *a, int n, int j) {
  int val = a[j];
  for (;;) {
    int j_rgt = 2 * j + 2;
    if (j_rgt < n) { // two children
      int j_lft = j_rgt - 1;
      if (a[j_lft] > a[j_rgt]) {
        if (val >= a[j_lft]) break;
        a[j] = a[j_lft];
        j = j_lft;
      } else {
        if (val >= a[j_rgt]) break;
        a[j] = a[j_rgt];
        j = j_rgt;
      }
    } else if (j_rgt == n) { // left child only
      int j_lft = j_rgt - 1;
      if (val >= a[j_lft]) break;
      a[j] = a[j_lft];
      j = j_lft;
      break;
    } else break;
  }
  a[j] = val;
}