src/sort.c

   1 /*
   2  * nao-ulib
   3  * Copyright (C) 2009 Daniel Borkmann <borkmann@gnumaniacs.org>
   4  * Copyright (C) 2009 Thomas Reinhardt <treinhar@imn.htwk-leipzig.de>
   5  * Copyright (C) 2009 Rico Tilgner <rtilgner@imn.htwk-leipzig.de>
   6  * Subject to the GPL.
   7  * Nao-Team HTWK,
   8  * Faculty of Computer Science, Mathematics and Natural Sciences,
   9  * Leipzig University of Applied Sciences (HTWK Leipzig)
  10  */
  11
  12 #include <stdio.h>
  13
  14 #include "xmalloc.h"
  15 #include "sort.h"
  16
  17 static void merge(int lo, int m, int hi, float *a, float *b)
  18 {
  19         int i, j, k;
  20
  21         i = 0; j = lo;
  22         while (j <= m)
  23                 b[i++] = a[j++];
  24
  25         i = 0; k = lo;
  26         while (k < j && j <= hi)
  27                 if (b[i] <= a[j])
  28                         a[k++] = b[i++];
  29                 else
  30                         a[k++] = a[j++];
  31
  32         while (k < j)
  33                 a[k++] = b[i++];
  34 }
  35
  36 static inline void mergesort(int lo, int hi, float *a, float *b)
  37 {
  38         if (lo < hi) {
  39                 int m = (lo + hi) / 2;
  40
  41                 mergesort(lo, m, a, b);
  42                 mergesort(m + 1, hi, a, b);
  43                 merge(lo, m, hi, a, b);
  44         }
  45 }
  46
  47 void sort(float *a, size_t n)
  48 {
  49         float *b = xmalloc(n * sizeof(float));
  50         mergesort(0, n - 1, a, b);
  51         xfree(b);
  52 }