算法实现/排序/归并排序
你从一个无序序列开始。你创建N个空的队列。你循环遍历要排序的每个项目。在每次循环迭代中，你查看键中的最后一个元素。你将该项目移到与该元素对应的队列的末尾。当你完成循环时，你将所有队列连接在一起形成另一个序列。然后，你重新应用描述的程序，但查看键中的倒数第二个元素。你一直这样做，直到你遍历了每个键。当你完成此过程时，生成的序列将按上述方式排序。
键以以下方式比较：令ka为一个项目（称为项目A）的键，令kb为另一个项目（称为项目B）的键。令ka(i)为键ka中的第i个条目，其中第一个条目在索引0处。令i = 0。如果键的长度小于i个元素，则键相等。如果ka(i) < kb(i)，则项目A在项目B之前排序。如果ka(i) > kb(i)，则项目B在项目A之前排序。如果ka(i) = kb(i)，则将i加1，并返回“令i = 0”下的行。
令ni为要排序的序列中的项目数。N是每个键元素可以取的整数的个数。令nk为每个项目中的键数。
因此，对序列进行排序的总时间为O(nk(ni + N))。
朴素实现，翻译自维基百科上的伪代码。
(defmacro
apenda-primeiro (ret1 left1)
"Appends first element of left1 to right1, and removes first element from left1."
`(progn
(setf ,ret1 (if (eq ,ret1 nil) (cons (car ,left1) nil) (append ,ret1 (cons (car ,left1) nil))))
(setf ,left1 (cdr ,left1))))
(defun
merge-func (left right)
"Our very own merge function, takes two lists, left and right, as arguments, and returns a new merged list."
(let (ret)
(loop
(if (or (not (null left)) (not (null right)))
(progn
(if (and (not (null left)) (not (null right)))
(if (<= (car left) (car right))
(apenda-primeiro ret left)
(apenda-primeiro ret right))
(if (not (null left))
(apenda-primeiro ret left)
(if (not (null right))
(apenda-primeiro ret right)))))
(return)))
ret))
(defun
merge-sort (m)
"Merge-sort proper. Takes a list m as input and returns a new, sorted list; doesn't touch the input."
(let* ((tam (length m))
(mid (ceiling (/ tam 2)))
(left)
(right))
(if (<= tam 1)
m
(progn
(loop for n from 0 to (- mid 1) do
(apenda-primeiro left m))
(loop for n from mid to (- tam 1) do
(apenda-primeiro right m))
(setf left (merge-sort left))
(setf right (merge-sort right))
(merge-func left right)))))
以某种更具功能性的风格进行更简单的实现。
(defun sort-func (frst scond &optional (sorted nil))
"Sorts the elements from the first and second list in ascending order and puts them in `sorted`"
(cond ((and (null frst) (null scond)) sorted)
((null frst) (append (reverse sorted) scond))
((null scond) (append (reverse sorted) frst))
(t (let ((x (first frst))
(y (first scond)))
(if (< x y)
(sort-func (rest frst) scond (push x sorted))
(sort-func frst (rest scond) (push y sorted)))))))
(defun merge-sort (lst)
"Divides the elements in `lst` into individual elements and sorts them"
(when (not (null lst))
(let ((divided (mapcar #'(lambda (x) (list x)) lst)))
(labels ((merge-func (div-list &optional (combined '())) ; merges the elements in ascending order
(if div-list
(merge-func (rest (rest div-list)) (push (sort-func (first div-list) (second div-list)) combined))
combined))
(final-merge (div-list) ; runs merge-func until all elements have been reconciled
(if (> (length div-list) 1)
(final-merge (merge-func div-list))
div-list)))
(final-merge divided)))))
///function:
mergeSort(name_array);
//tipo Data used:
typedef struct data{
char*some;
int data;
} DATA;
typedef struct _nodo{
int key;
DATA data;
}nodo;
///n is kept as global
int n;
void merge(nodo*a,nodo*aux,int left,int right,int rightEnd){
int i,num,temp,leftEnd=right-1;
temp=left;
num=rightEnd-left+1;
while((left<=leftEnd)&&(right<=rightEnd)){
if(a[left].key<=a[right].key){
aux[temp++]=a[left++];
}
else{
aux[temp++]=a[right++];
}
}
while(left<=leftEnd){
aux[temp++]=a[left++];
}
while(right<=rightEnd){
aux[temp++]=a[right++];
}
for (i=1;i<=num;i++,rightEnd--){
a[rightEnd]=aux[rightEnd];
}
}
void mSort(nodo*a,nodo*aux,int left,int right){
int center;
if (left<right){
center=(left+right)/2;
mSort(a,aux,left,center);
mSort(a,aux,center+1,right);
merge(a,aux,left,center+1,right);
}
}
void mergeSort(nodo*p){
nodo*temp=(nodo*)malloc(sizeof(nodo)*n);
mSort(p,temp,0,n-1);
free(temp);
}
使用C++14标准库的递归实现。
#include <iterator>
#include <algorithm>
#include <functional>
template <typename BidirIt, typename Compare = std::less<>>
void merge_sort(BidirIt first, BidirIt last, Compare cmp = Compare {})
{
const auto n = std::distance(first, last);
if (n > 1) {
const auto middle = std::next(first, n / 2);
merge_sort(first, middle, cmp);
merge_sort(middle, last, cmp);
std::inplace_merge(first, middle, last, cmp);
}
}
#include <vector>
int main()
{
std::vector<int> v {3, -2, 1, 5, -9, 10, 3, -3, 2};
merge_sort(std::begin(v), std::end(v)); // sort increasing
merge_sort(std::begin(v), std::end(v), std::greater<> {}); // sort decreasing
}
subroutine Merge(A,NA,B,NB,C,NC)
integer, intent(in) :: NA,NB,NC ! Normal usage: NA+NB = NC
integer, intent(in out) :: A(NA) ! B overlays C(NA+1:NC)
integer, intent(in) :: B(NB)
integer, intent(in out) :: C(NC)
integer :: I,J,K
I = 1; J = 1; K = 1;
do while(I <= NA .and. J <= NB)
if (A(I) <= B(J)) then
C(K) = A(I)
I = I+1
else
C(K) = B(J)
J = J+1
endif
K = K + 1
enddo
do while (I <= NA)
C(K) = A(I)
I = I + 1
K = K + 1
enddo
return
end subroutine merge
recursive subroutine MergeSort(A,N,T)
integer, intent(in) :: N
integer, dimension(N), intent(in out) :: A
integer, dimension((N+1)/2), intent (out) :: T
integer :: NA,NB,V
if (N < 2) return
if (N == 2) then
if (A(1) > A(2)) then
V = A(1)
A(1) = A(2)
A(2) = V
endif
return
endif
NA=(N+1)/2
NB=N-NA
call MergeSort(A,NA,T)
call MergeSort(A(NA+1),NB,T)
if (A(NA) > A(NA+1)) then
T(1:NA)=A(1:NA)
call Merge(T,NA,A(NA+1),NB,A,N)
endif
return
end subroutine MergeSort
program TestMergeSort
integer, parameter :: N = 8
integer, dimension(N) :: A = (/ 1, 5, 2, 7, 3, 9, 4, 6 /)
integer, dimension ((N+1)/2) :: T
call MergeSort(A,N,T)
write(*,'(A,/,10I3)')'Sorted array :',A
end program TestMergeSort
function merge_sort(arr)
if length(arr) <= 1
return arr
end
middle = trunc(Int, length(arr) / 2)
L = arr[1:middle]
R = arr[middle+1:end]
merge_sort(L)
merge_sort(R)
i = j = k = 1
while i <= length(L) && j <= length(R)
if L[i] < R[j]
arr[k] = L[i]
i+=1
else
arr[k] = R[j]
j+=1
end
k+=1
end
while i <= length(L)
arr[k] = L[i]
i+=1
k+=1
end
while j <= length(R)
arr[k] = R[j]
j+=1
k+=1
end
arr
end
(define (mergesort x)
(if (= 0 (length x))
'()
;else
(if (= (length x) 1)
x
;else
(combine (mergesort (firstHalf x (/ (length x) 2))) (mergesort (lastHalf x (/ (length x) 2)))
)
)
)
)
(define (combine list1 list2)
(if (null? list1) list2
;else
(if (null? list2) list1
;else
(if (<= (car list1) (car list2))
;car of list 1 is second element of list 2
(cons (car list1) (combine (cdr list1) list2))
;else
(cons (car list2) (combine list1 (cdr list2)))
)
)
)
)
(define (firstHalf L N)
(if (= N 0)
null
)
(if (or (= N 1) (< N 2))
(list (car L))
;else
(cons (car L) (firstHalf (cdr L) (- N 1)))))
(define (lastHalf L N)
(if (= N 0) L); Base Case
(if (or (= N 1) (< N 2))
(cdr L)
;else
(lastHalf (cdr L) (- N 1)))
)
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
where
(ys,zs) = splitAt (length xs `div` 2) xs
merge [] y=y
merge x []=x
merge (x:xs) (y:ys)
| x<=y = x:merge xs (y:ys)
| otherwise = y:merge (x:xs) ys
一个稍微更高效的版本只遍历输入列表一次以进行拆分（注意，length在Haskell中需要线性时间）
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
where (ys,zs) = split xs
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x<=y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
split [] = ([], [])
split [x] = ([x], [])
split (x:y:xs) = (x:l, y:r)
where (l, r) = split xs
function merge(sequence left, sequence right)
sequence result = {}
while length(left)>0 and length(right)>0 do
if left[1]<=right[1] then
result = append(result, left[1])
left = left[2..$]
else
result = append(result, right[1])
right = right[2..$]
end if
end while
return result & left & right
end function
function mergesort(sequence m)
sequence left, right
integer middle
if length(m)<=1 then
return m
end if
middle = floor(length(m)/2)
left = mergesort(m[1..middle])
right = mergesort(m[middle+1..$])
if left[$]<=right[1] then
return left & right
elsif right[$]<=left[1] then
return right & left
end if
return merge(left, right)
end function
这是一个与ISO-Prolog兼容的归并排序实现。
mergesort(L, Sorted) :-
once(mergesort_r(L, Sorted)).
mergesort_r([], []).
mergesort_r([X], [X]).
mergesort_r(L, Sorted) :-
split(L, Left, Right),
mergesort_r(Left, SortedL),
mergesort_r(Right, SortedR),
merge(SortedL, SortedR, Sorted).
% Split list into two roughly equal-sized lists.
split([], [], []).
split([X], [X], []).
split([X,Y|Xs], [X|Left], [Y|Right]) :-
split(Xs, Left, Right).
% Merge two sorted lists into one.
merge(Left, [], Left).
merge([], Right, Right).
merge([X|Left], [Y|Right], [Z|Merged]) :-
(X @< Y ->
Z = X,
merge(Left, [Y|Right], Merged)
;
Z = Y,
merge([X|Left], Right, Merged)
).
一个“标准”归并排序
from heapq import merge
def mergesort(w):
"""Sort list w and return it."""
if len(w)<2:
return w
else:
# sort the two halves of list w recursively with mergesort and merge them
return merge(mergesort(w[:len(w)//2]), mergesort(w[len(w)//2:]))
一种替代方法，使用递归算法在原地执行合并（除了跟踪递归的O(log n)开销外）在O(n log n)时间内
def merge(lst, frm, pivot, to, len1, len2):
if len1==0 or len2==0: return
if len1+len2 == 2:
if lst([pivot])<lst[frm]: lst[pivot], lst[frm] = lst[frm], lst[pivot]
return
if len1 > len2:
len11 = len1/2
firstcut, secondcut, length = frm+len11, pivot, to-pivot
while length > 0:
half = length/2
mid = secondcut+half
if lst[mid]<lst[firstcut]: secondcut, length = mid+1, length-half-1
else: length = half
len22 = secondcut - pivot
else:
len22 = len2/2
firstcut, secondcut, length = frm, pivot+len22, pivot-frm
while length > 0:
half = length/2
mid = firstcut+half
if lst[secondcut]<lst[mid]: length = half
else: firstcut, length = mid+1, length-half-1
len11 = firstcut-frm
if firstcut!=pivot and pivot!=secondcut:
n, m = secondcut-firstcut, pivot-firstcut
while m != 0: n, m = m, n%m
while n != 0:
n -= 1
p1, p2 = firstcut+n, n+pivot
val, shift = lst[p1], p2-p1
while p2 != firstcut+n:
lst[p1], p1 = lst[p2], p2
if secondcut-p2>shift: p2 += shift
else: p2 = pivot-secondcut+p2
lst[p1] = val
newmid = firstcut+len22
merge(lst, frm, firstcut, newmid, len11, len22)
merge(lst, newmid, secondcut, to, len1-len11, len2-len22)
def sort(lst, frm=0, to=None):
if to is None: to = len(lst)
if to-frm<2: return
middle = (frm+to)/2
sort(lst, frm, middle)
sort(lst, middle, to)
merge(lst, frm, middle, to, middle-frm, to-middle)
def merge_sort(array)
return array if array.size <= 1
mid = array.size / 2
merge(merge_sort(array[0...mid]), merge_sort(array[mid...array.size]))
end
def merge(left, right)
result = []
until left.empty? || right.empty?
result << (left[0] <= right[0] ? left : right).shift
end
result.concat(left).concat(right)
end
sort [] = []
sort [x] = [x]
sort array = merge (sort left) (sort right)
where
left = [array!y | y <- [0..mid]]
right = [array!y | y <- [(mid+1)..max]]
max = #array - 1
mid = max div 2
fun mergesort [] = []
| mergesort [x] = [x]
| mergesort lst =
let fun merge ([],ys) = ys (*merges two sorted lists to form a sorted list *)
| merge (xs,[]) = xs
| merge (x::xs,y::ys) =
if x<y then
x::merge (xs,y::ys)
else
y::merge (x::xs,ys)
;
val half = length(lst) div 2;
in
merge (mergesort (List.take (lst, half)),mergesort (List.drop (lst, half)))
end
;
public int[] mergeSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
// if the array has more than 1 element, we need to split it and merge the sorted halves
if(array.length > 1)
{
// number of elements in sub-array 1
// if odd, sub-array 1 has the smaller half of the elements
// e.g. if 7 elements total, sub-array 1 will have 3, and sub-array 2 will have 4
int elementsInA1 = array.length / 2;
// we initialize the length of sub-array 2 to
// equal the total length minus the length of sub-array 1
int elementsInA2 = array.length - elementsInA1;
// declare and initialize the two arrays once we've determined their sizes
int arr1[] = new int[elementsInA1];
int arr2[] = new int[elementsInA2];
// copy the first part of 'array' into 'arr1', causing arr1 to become full
for(int i = 0; i < elementsInA1; i++)
arr1[i] = array[i];
// copy the remaining elements of 'array' into 'arr2', causing arr2 to become full
for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
arr2[i - elementsInA1] = array[i];
// recursively call mergeSort on each of the two sub-arrays that we've just created
// note: when mergeSort returns, arr1 and arr2 will both be sorted!
// it's not magic, the merging is done below, that's how mergesort works :)
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
// the three variables below are indexes that we'll need for merging
// [i] stores the index of the main array. it will be used to let us
// know where to place the smallest element from the two sub-arrays.
// [j] stores the index of which element from arr1 is currently being compared
// [k] stores the index of which element from arr2 is currently being compared
int i = 0, j = 0, k = 0;
// the below loop will run until one of the sub-arrays becomes empty
// in my implementation, it means until the index equals the length of the sub-array
while(arr1.length != j && arr2.length != k)
{
// if the current element of arr1 is less than current element of arr2
if(arr1[j] < arr2[k])
{
// copy the current element of arr1 into the final array
array[i] = arr1[j];
// increase the index of the final array to avoid replacing the element
// which we've just added
i++;
// increase the index of arr1 to avoid comparing the element
// which we've just added
j++;
}
// if the current element of arr2 is less than current element of arr1
else
{
// copy the current element of arr2 into the final array
array[i] = arr2[k];
// increase the index of the final array to avoid replacing the element
// which we've just added
i++;
// increase the index of arr2 to avoid comparing the element
// which we've just added
k++;
}
}
// at this point, one of the sub-arrays has been exhausted and there are no more
// elements in it to compare. this means that all the elements in the remaining
// array are the highest (and sorted), so it's safe to copy them all into the
// final array.
while(arr1.length != j)
{
array[i] = arr1[j];
i++;
j++;
}
while(arr2.length != k)
{
array[i] = arr2[k];
i++;
k++;
}
}
// return the sorted array to the caller of the function
return array;
}
JavaScript
[编辑 | 编辑源代码];(function() {
var defaultComparator = function (a, b) {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
Array.prototype.mergeSort = function( comparator ) {
var i, j, k,
firstHalf,
secondHalf,
arr1,
arr2;
if (typeof comparator != "function") { comparator = defaultComparator; }
if (this.length > 1) {
firstHalf = Math.floor(this.length / 2);
secondHalf = this.length - firstHalf;
arr1 = [];
arr2 = [];
for (i = 0; i < firstHalf; i++) {
arr1[i] = this[i];
}
for(i = firstHalf; i < firstHalf + secondHalf; i++) {
arr2[i - firstHalf] = this[i];
}
arr1.mergeSort( comparator );
arr2.mergeSort( comparator );
i=j=k=0;
while(arr1.length != j && arr2.length != k) {
if ( comparator( arr1[j], arr2[k] ) <= 0 ) {
this[i] = arr1[j];
i++;
j++;
}
else {
this[i] = arr2[k];
i++;
k++;
}
}
while (arr1.length != j) {
this[i] = arr1[j];
i++;
j++;
}
while (arr2.length != k) {
this[i] = arr2[k];
i++;
k++;
}
}
}
})();
分成两个函数
function mergesort(list){
return (list.length < 2) ? list : merge(mergesort(list.splice(0, list.length >> 1)), mergesort(list));
}
function merge(left, right){
var sorted = [];
while (left.length && right.length)
sorted.push(left[0] <= right[0]? left.shift() : right.shift());
while(left.length)
sorted.push(left.shift());
while(right.length)
sorted.push(right.shift());
return sorted;
}
use sort '_mergesort';
sort @array;
function merge_sort(array $left, array $right) {
$result = [];
while (count($left) && count($right))
($left[0] < $right[0]) ? $result[] = array_shift($left) : $result[] = array_shift($right);
return array_merge($result, $left, $right);
}
function merge(array $arrayToSort) {
if (count($arrayToSort) == 1)
return $arrayToSort;
$left = merge(array_slice($arrayToSort, 0, count($arrayToSort) / 2));
$right = merge(array_slice($arrayToSort, count($arrayToSort) / 2, count($arrayToSort)));
return merge_sort($left, $right);
}
def mergeSort(def list){
if (list.size() <= 1) { return list }
else {
center = list.size() / 2
left = list[0..center]
right = list[center..list.size() - 1]
merge(mergeSort(left), mergeSort(right))
}
}
def merge(def left, def right){
def sorted = []
while(left.size() > 0 && right.size() > 0)
if(left.get(0) <= right.get(0)){
sorted << left.remove(0)
}else{
sorted << right.remove(0)
}
sorted = sorted + left + right
return sorted
}
class
APPLICATION
feature -- Algorithm
mergesort (a: ARRAY [INTEGER]; l, r: INTEGER)
-- Recursive mergesort
local
m: INTEGER
do
if l < r then
m := (l + r) // 2
mergesort(a, l, m)
mergesort(a, m + 1, r)
merge(a, l, m, r)
end
end
feature -- Utility feature
merge (a: ARRAY [INTEGER]; l, m, r: INTEGER)
-- The merge feature of all mergesort variants
local
b: ARRAY [INTEGER]
h, i, j, k: INTEGER
do
i := l
j := m + 1
k := l
create b.make (l, r)
from
until
i > m or j > r
loop
-- Begins the merge and copies it into an array `b'
if a.item (i) <= a.item (j) then
b.item (k) := a.item (i)
i := i + 1
elseif a.item (i) > a.item (j) then
b.item (k) := a.item (j)
j := j + 1
end
k := k + 1
end
-- Finishes the copy of the uncopied part of the array
if i > m then
from
h := j
until
h > r
loop
b.item (k + h - j) := a.item (h)
h := h + 1
end
elseif j > m then
from
h := i
until
h > m
loop
b.item (k + h - i) := a.item (h)
h := h + 1
end
end
-- Begins the copy to the real array
from
h := l
until
h > r
loop
a.item (h) := b.item (h)
h := h + 1
end
end
feature -- Attributes
array: ARRAY [INTEGER]
end
public class MergeSort<T> where T : IComparable
{
public T[] Sort(T[] source)
{
T[] sorted = this.Split(source);
return sorted;
}
private T[] Split(T[] from)
{
if (from.Length == 1)
{
// size <= 1 considered sorted
return from;
}
else
{
int iMiddle = from.Length / 2;
T[] left = new T[iMiddle];
for (int i = 0; i < iMiddle; i++)
{
left[i] = from[i];
}
T[] right = new T[from.Length - iMiddle];
for (int i = iMiddle; i < from.Length; i++)
{
right[i - iMiddle] = from[i];
}
// Single threaded version
T[] sLeft = this.Split(left);
T[] sRight = this.Split(right);
T[] sorted = this.Merge(sLeft, sRight);
return sorted;
}
}
private T[] Merge(T[] left, T[] right)
{
// each array will individually be sorted.
// Do a sort of card merge to merge them in a sorted sequence
int leftLen = left.Length;
int rightLen = right.Length;
T[] sorted = new T[leftLen + rightLen];
int lIndex = 0;
int rIndex = 0;
int currentIndex = 0;
while (lIndex < leftLen || rIndex < rightLen)
{
// If either has had all elements taken, just take remaining from the other.
// If not, compare the two current and take the lower.
if (lIndex >= leftLen)
{
sorted[currentIndex] = right[rIndex];
rIndex++;
currentIndex++;
}
else if (rIndex >= rightLen)
{
sorted[currentIndex] = left[lIndex];
lIndex++;
currentIndex++;
}
else if (left[lIndex].CompareTo(right[rIndex]) >= 0)
{
// l > r, so r goes into dest
sorted[currentIndex] = right[rIndex];
rIndex++;
currentIndex++;
}
else
{
sorted[currentIndex] = left[lIndex];
lIndex++;
currentIndex++;
}
}
return sorted;
}
}
const maxA = 1000;
type TElem = integer;
TArray = array[1..maxA]of TElem;
procedure merge(var A:TArray;p,q,r:integer);
var i,j,k,n1,n2:integer;
B:TArray;
begin
n1 := q - p + 1;
n2 := r - q;
for k := p to r do
B[k - p + 1] := A[k];
i := 1;
j :=n1 + 1;
k := p;
while(i <= n1)and(j <= n1 + n2)do
begin
if B[i] <= B[j] then
begin
A[k] := B[i];
i := i + 1;
end
else
begin
A[k] := B[j];
j := j + 1;
end;
k := k + 1;
end;
while i <= n1 do
begin
A[k] := B[i];
i := i + 1;
k := k + 1;
end;
while j <= n1 + n2 do
begin
A[k] := B[j];
j := j + 1;
k := k + 1;
end;
end;
(* Recursive version of merge sort *)
procedure mergeSort(var A:TArray;p,r:integer);
var q:integer;
begin
if p < r then
begin
q := (p + r) div 2;
mergeSort(A,p,q);
mergeSort(A,q + 1,r);
merge(A,p,q,r);
end;
end;
(* Iterative version of merge sort *)
procedure mergeSort(var A:TArray;n:integer);
var p,q,r,k:integer;
begin
k := 1;
while k <= n do
begin
p := 1;
while p + k <= n do
begin
q := p + k - 1;
if p + 2 * k - 1 < n then
r := p + 2 * k - 1
else
r := n;
merge(A,p,q,r);
p := p + 2 * k;
end;
k := k * 2;
end;
end;
使用函子创建模块，专门用于使用特定比较函数对给定类型的列表进行排序
module type Comparable = sig
type t
val compare: t -> t -> int
end
module MakeSorter(M : Comparable) = struct
(** Split list into two roughly equal halves *)
let partition (lst: M.t list) =
let rec helper lst left right =
match lst with
| [ ] -> left, right
| x :: [ ] -> x :: left, right
| x :: y :: xs -> helper xs (x :: left) (y :: right) in
helper lst [] []
(** Merge two sorted lists *)
let rec merge left right =
match left, right with
| _, [ ] -> left (* Emmpty right list *)
| [ ], _ -> right (* Empty left list *)
| x :: xs, y :: _ when (M.compare x y) < 0 -> x :: merge xs right (* First element of left is less than first element of right *)
| _, y :: ys -> y :: merge left ys (* First element of right is greater than or equal to first element of left *)
let rec sort lst =
match lst with
| [ ] | _ :: [ ] -> lst (* Empty and single element lists are always sorted *)
| lst ->
let left, right = partition lst in
merge (sort left) (sort right)
end
module StringSort = MakeSorter(String)
let () =
let animals = [ "dog"; "cow"; "ant"; "zebra"; "parrot" ] in
let sorted_animals = StringSort.sort animals in
List.iter print_endline sorted_animals