00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX_SORT_LIST_HPP
00014 #define __MMX_SORT_LIST_HPP
00015 #include <basix/list.hpp>
00016
00019
00020 namespace mmx {
00021 #define TMPL template<typename C>
00022 #define List list<C>
00023
00026 TMPL void
00027 split (const List& l, nat n, List& head, List& tail) {
00028 if (n == 0) {
00029 head= List ();
00030 tail= l;
00031 }
00032 else {
00033 split (cdr (l), n-1, head, tail);
00034 head= cons (car (l), head);
00035 }
00036 }
00037
00040 TMPL List
00041 merge (const List& head, const List& tail, int (*cmp) (const C&, const C&)) {
00042 if (is_nil (head)) return tail;
00043 if (is_nil (tail)) return head;
00044 if (cmp (car (head), car (tail)) <= 0)
00045 return cons (car (head), merge (cdr (head), tail, cmp));
00046 return cons (car (tail), merge (head, cdr (tail), cmp));
00047 }
00048
00053 TMPL List
00054 sort (const List& l, int (*cmp) (const C&, const C&)) {
00055 nat n= N(l);
00056 if (n <= 1) return l;
00057 List head, tail;
00058 split (l, n>>1, head, tail);
00059 head= sort (head, cmp);
00060 tail= sort (tail, cmp);
00061 return merge (head, tail, cmp);
00062 }
00063
00064 #undef TMPL
00065 #undef List
00066 }
00067 #endif // __MMX_LIST_HPP