Heapsort implementation for Sybase Aleri (SPLASH)

heapsort.xmlf

// Pretty literal implementation of the heap sort documented on Wikipedia
// http://en.wikipedia.org/wiki/Heapsort
// Datatypes can trivially be changed to others

int32 heap_sort_double (vector(double) data) {
  heapify_double(data);
  
  int32 v_end := size(data) - 1;
  while (v_end > 0) {
    swap_double (data,v_end,0);
    sift_down_double (data, 0, v_end - 1);
    v_end--;
  }
}

int32 heapify_double (vector(double) data) {
  int32 v_size := size(data);
  int32 start := size(data) / 2 - 1;
  while (start >= 0) {
    sift_down_double (data, start, v_size - 1);
    start--;
  }
}

int32 sift_down_double (vector(double) data, int32 start, int32 v_end) {
  int32 root := start;
  while (root * 2 + 1 <= v_end) {
    int32 child := root * 2 + 1;
    int32 swap := root;
    if (data[swap] < data[child]) {
      swap := child;
    }
    if (child + 1 <= v_end and data[swap] < data[child + 1]) {
      swap := child + 1;
    }
    if (swap != root) {
      swap_double (data, root, swap);
      root := swap;
    }
    else {
      return 0;
    }
  }
}

int32 swap_double (vector(double) data, int32 el1, int32 el2) {
  double temp := data[el1];
  data[el1] := data[el2];
  data[el2] := temp;
}