% ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % % QUICKSORT % % ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % function qsort(a) = if (#a < 2) then a else let pivot = a[#a/2]; lesser = {e in a| e < pivot}; equal = {e in a| e == pivot}; greater = {e in a| e > pivot}; result = {qsort(v): v in [lesser,greater]}; in result[0] ++ equal ++ result[1] \$ % ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % % BATCHER'S BITONIC SORT % % W = O(n \lg^2 n) % % S = O(\lg^2 n) % % ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % function bitonic_sort(a) = if (#a == 1) then a else let bot = subseq(a,0,#a/2); top = subseq(a,#a/2,#a); mins = {min(bot,top):bot;top}; maxs = {max(bot,top):bot;top}; in flatten({bitonic_sort(x) : x in [mins,maxs]}) \$ function batcher_sort(a) = if (#a == 1) then a else let b = {batcher_sort(x) : x in bottop(a)}; in bitonic_sort(b[0]++reverse(b[1])) \$ % ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % % BATCHER'S ODD-EVEN MERGESORT % % W = O(n \lg^2 n) % % S = O(\lg^2 n) % % ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; % % The length of A and B must be equal and a power of 2 % function odd_even_merge(a,b) = if (#a > 1) then let b = {odd_even_merge(a,b) : a in [odd_elts(a),even_elts(a)] ; b in [odd_elts(b),even_elts(b)]}; odd, even = b[0],b[1] in interleave({min(odd,even):odd;even},{max(odd,even):odd;even}) else if (a[0] < b[0]) then a++b else b++a \$ % The length of a must be a power of 2. % function odd_even_merge_sort(a) = if (#a == 1) then a else let b = {odd_even_merge_sort(x) : x in bottop(a)}; in odd_even_merge(b[0],b[1]) \$