Subversion Repositories heap_sorter

#include <stdint.h>

#include <stdio.h>

#include <string.h>

#include "wz_hsort.h"

sort_data sort_mem[SORT_LEN];

sort_data heap_sort (sort_data val)

{

  sort_data res;

  sort_data cur = val;

  int lev, offs, top, left, right;

  cur = sort_mem[1];

  if (val.key <= cur.key)

    return val;                 //No need to update the heap

  else

    {

      res = cur;

      cur = val;

      offs = 0;

      for (lev = 1; lev <= NM; lev++)

        {

          top = (1 << (lev - 1)) + offs;

          left = (2 << (lev - 1)) + offs;

          right = (3 << (lev - 1)) + offs;

          if ((lev == NM) ||

              ((cur.key <= sort_mem[left].key) &&

               (cur.key <= sort_mem[right].key)))

            {

              sort_mem[top] = cur;

              break;

            }

          else if ((sort_mem[left].key < cur.key) &&

                   (sort_mem[left].key <= sort_mem[right].key))

            {

              sort_mem[top] = sort_mem[left];

            }

          else if (sort_mem[right].key < cur.key)

            {

              sort_mem[top] = sort_mem[right];

              offs += (1 << (lev - 1));

            }

          else

            {

              printf ("impossible!!!\n");

            }

        }

    }

  return res;

}