Algorithm Implementation/Sorting/Merge sort
From Wikibooks, the open-content textbooks collection
< Algorithm Implementation | Sorting(Redirected from Algorithm implementation/Sorting/Merge sort)
Contents |
[edit] C
/* Mix two sorted tables in one and split the result into these two tables. */ int *Mix(int *tab1,int *tab2,int count1,int count2) { int i,i1,i2; i = i1 = i2 = 0; int * temp = (int *)malloc(sizeof(int)*(count1+count2)); while((i1<count1) && (i2<count2)) { while((i1<count1) && (*(tab1+i1)<=*(tab2+i2))) { *(temp+i++) = *(tab1+i1); i1++; } if (i1<count1) { while((i2<count2) && (*(tab2+i2)<=*(tab1+i1))) { *(temp+i++) = *(tab2+i2); i2++; } } } memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int)); memcpy(tab1,temp,count1*sizeof(int)); memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int)); memcpy(tab2,temp+count1,count2*sizeof(int)); /* These two lines can be: */ /* memcpy(tab2,temp+count1,i2*sizeof(int)); */ free(temp); } /* MergeSort a table of integer of size count. (Has been tested.) */ void MergeSort(int *tab,int count) { if (count==1) return; MergeSort(tab,count/2); MergeSort(tab+count/2,(count+1)/2); Mix(tab,tab+count/2,count/2,(count+1)/2); }
[edit] Fortran
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
[edit] Scheme
(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))) )
[edit] Haskell
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
A slightly more lazy version that doesn't check the length of the list each iteration:
sort :: Ord a => [a] -> [a]
sort [] = []
sort [x] = [x]
sort xs = merge (sort ys) (sort zs)
where
(ys,zs) = (odds xs, evens 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
odds [] = []
odds [x] = [x]
odds (x:_:xs) = x:odds xs
evens [] = []
evens [x] = []
evens (_:x:xs) = x:evens xs
[edit] Prolog
This is an ISO-Prolog compatible implementation of merge sort with the exception of the predicate append(-list, -list, -list), which is available in most Prolog implementations. Special prolog dialects might provide some of the predicates used in this implementation.
% Merge-Sort: ms(<source>, <result>) % ms([], []). ms(Xs, Rs) :- len(Xs, L), ms(Xs, Rs, L), !. % Merge-Sort: ms(<source>, <result>, len). Here len is the number of elements in <source> which will be sorted % ms([], [], _). ms(Xs, Xs, 0) :- !. ms(Xs, Xs, 1) :- !. ms(Xs, Ys, N) :- N > 1, N1 is N//2, N2 is N-N1, split(Xs, XAs, XBs, XCs, N1, N), ms(XAs, XAMs, N1), ms(XBs, XBMs, N2), merge(XAMs, XBMs, Yss), append(Yss, XCs, Ys), !. % Merge of lists: merge(<list1>, <list2>, <result>) % merge([], Xs, Xs). merge(Xs, [], Xs). merge([X|Xs], [Y|Ys], Zs) :- X =< Y -> (merge(Xs, [Y|Ys], Zss), append([X], Zss, Zs), !); (merge([X|Xs], Ys, Zss), append([Y], Zss, Zs), !). % Splits a list into three chunks at the positions given. Positions need not be within the bounds of the list % split([], [], [], [], _, _). split(Xs, [], [], Xs, 0, 0). split(Xs, [], As, Bs, 0, N) :- 0 =< N, split(Xs, As, Bs, N), !. split(Xs, As, [], Bs, N, N) :- 0 =< N, split(Xs, As, Bs, N), !. split(Xs, As, Bs, Cs, N, M) :- 0 < N, N =< M, Xs = [X|Xss], As = [X|Ass], N1 is N-1, M1 is M-1, split(Xss, Ass, Bs, Cs, N1, M1), !. % Length of a list % len([], 0). len([_|Xs], N) :- len(Xs, N1), N is N1+1. The above implementation assumes that comparison is done with the '=<' operator. Instead, one can pass in a rule for comparing list entries. Evaluation might then be effected as follows: % comp(+functor, +atomic, + atomic, -integer): Compares atomic values % functor: A 3-arguent predicate; this predicate implements the comparison % atomic : Atomic values % integer: Result, interpreted according to sign comp(F, X, Y, I) :- functor(F, N, 3), arg(1, F, X), arg(2, F, Y), arg(3, F, I), call(F).
[edit] Python
def mergesort(w): """Sort list w and return it.""" if len(w)<2: return w else: mid=len(w)//2 # sort the two halves of list w recursively with mergesort and merge them return merge(mergesort(w[:mid]), mergesort(w[mid:])) def merge(u, v): """Merge two sorted lists u and v together. Return the merged list r.""" r=[] while u and v: # pop the smaller element from the front of u or v and append it to list r r.append( u.pop(0) if u[0] < v[0] else v.pop(0) ) # extend result with the remaining end r.extend(u or v) return r
[edit] Ruby
def mergesort(list) return list if list.size <= 1 mid = list.size / 2 left = list[0, mid] right = list[mid, list.size] merge(mergesort(left), mergesort(right)) end def merge(left, right) sorted = [] until left.empty? or right.empty? if left.first <= right.first sorted << left.shift else sorted << right.shift end end sorted.concat(left).concat(right) end
[edit] Miranda
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
[edit] ML
(* I'm not sure whether take and drop are in the libraries, so I've included them for completeness *)
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))
;
fun take (0, xs) = [] (* take(l,xs) gets the first l elements of xs *)
| take (l, []) = raise Empty
| take (l, x::xs) = x::(take (l-1, xs))
;
fun drop (0, xs) = xs (* drop (l,xs) gets all but the first l elements of xs *)
| drop (l, []) = raise Empty
| drop (l, x::xs) = drop (l-1,xs)
;
val half = length(lst) div 2;
in
merge (mergesort (take (half, lst)),mergesort (drop (half, lst)))
end
;
[edit] Java
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 arr1 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; }
[edit] JavaScript
function mergeSort() { if(this.length > 1) { var firstHalf = Math.floor(this.length / 2); var secondHalf = this.length - firstHalf; var arr1 = new Array(firstHalf); var arr2 = new Array(secondHalf); for(var i = 0; i < firstHalf; i++) { arr1[i] = this[i]; } for(i = firstHalf; i < firstHalf + secondHalf; i++) { arr2[i - firstHalf] = this[i]; } arr1.mergeSort(); arr2.mergeSort(); var i=0; var j=0; var k=0; while(arr1.length != j && arr2.length != k) { if(arr1[j] < arr2[k]) { 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++; } } } Array.prototype.mergeSort = mergeSort;
[edit] C#
public IList MergeSort(IList list)
{
if (list.Count <= 1)
return list;
int mid = list.Count / 2;
IList left = new ArrayList();
IList right = new ArrayList();
for (int i = 0; i < mid; i++)
left.Add(list[i]);
for (int i = mid; i < list.Count; i++)
right.Add(list[i]);
return Merge(MergeSort(left), MergeSort(right));
}
public IList Merge(IList left, IList right)
{
IList rv = new ArrayList();
while (left.Count > 0 && right.Count > 0)
if (((IComparable)left[0]).CompareTo(right[0]) > 0)
{
rv.Add(right[0]);
right.RemoveAt(0);
}
else
{
rv.Add(left[0]);
left.RemoveAt(0);
}
for (int i = 0; i < left.Count; i++)
rv.Add(left[i]);
for (int i = 0; i < right.Count; i++)
rv.Add(right[i]);
return rv;
}
[edit] C++
Here is a recursive implementation of the merge sort using STL vectors (This is a naive implementation):
//! \brief Performs a recursive merge sort on the given vector //! \param vec The vector to be sorted using the merge sort //! \return The sorted resultant vector after merge sort is //! complete. vector<int> merge_sort(vector<int>& vec) { // Termination condition: List is completely sorted if it // only contains a single element. if(vec.size() == 1) { return vec; } // Determine the location of the middle element in the vector std::vector<int>::iterator middle = vec.begin() + (vec.size() / 2); vector<int> left(vec.begin(), middle); vector<int> right(middle, vec.end()); // Perform a merge sort on the two smaller vectors left = merge_sort(left); right = merge_sort(right); return merge(left, right); }
And here is the implementation of the merge function:
//! \brief Merges two sorted vectors into one sorted vector //! \param left A sorted vector of integers //! \param right A sorted vector of integers //! \return A sorted vector that is the result of merging two sorted //! vectors. vector<int> merge(const vector<int>& left, const vector<int>& right) { // Fill the resultant vector with sorted results from both vectors vector<int> result; unsigned left_it = 0, right_it = 0; while(left_it < left.size() && right_it < right.size()) { // If the left value is smaller than the right it goes next // into the resultant vector if(left[left_it] < right[right_it]) { result.push_back(left[left_it]); left_it++; } else { result.push_back(right[right_it]); right_it++; } } // Push the remaining data from both vectors onto the resultant while(left_it < left.size()) { result.push_back(left[left_it]); left_it++; } while(right_it < right.size()) { result.push_back(right[right_it]); right_it++; } return result; }
Here's another recursive implementation of the mergesort using arrays of variable length
#include <iostream> using namespace std; void merge(int a[], const int low, const int mid, const int high) { // Variables declaration. int * b = new int[high+1-low]; int h,i,j,k; h=low; i=0; j=mid+1; // Merges the two array's into b[] until the first one is finish while((h<=mid)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } // Completes the array filling in it the missing values if(h>mid) { for(k=j;k<=high;k++) { b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } // Prints into the original array for(k=0;k<=high-low;k++) { a[k+low]=b[k]; } delete[] b; } void merge_sort(int a[], const int low, const int high) // Rekursive sort ... { int mid; if(low<high) { mid=(low+high)/2; merge_sort(a, low,mid); merge_sort(a, mid+1,high); merge(a, low,mid,high); } } int _tmain(int argc, _TCHAR* argv[]) { int arraySize; // a[] is the array to be sorted. ArraySize is the size of a[] ... merge_sort(a, 0, (arraySize-1) ); // would be more natural to use merge_sort(a, 0, arraySize ), so please try ;-) // some work return 0; }
[edit] PHP
//Aux functions:slice and merge //slice_array:Create a new array from an exist array key $from to $to function slice_array($arr,$from,$to){ if($from>$to) return $arr; elseif($from==$to) return $arr[$from]; if(!is_array($arr)||count($arr)==1) {return $arr;} else{ $new=array();$a=$to-$from; for($i=0;$i<$a;$i++){ $new[$i]=$arr[$from++]; } } return $new; } //merge_array: create a new array from two exist arrays, order is $x, $y. function merge_array($x,$y){ $new=array(); for($i=0;$i<count($x);$i++){ $new[$i]=$x[$i]; } for($j=0;$j<count($y);$j++){ $new[count($x)+$j]=$y[$j]; } return $new; } //Main Script function MergeSort($a){ if (count($a)>1){ $cent=floor(count($a)/2); $b=MergeSort(slice_array($a,0,$cent)); $c=MergeSort(slice_array($a,$cent,count($a))); return merge($b,$c,$a); }else{return $a;} } function merge($b,$c,$a){ $i=$j=$k=0; $p=count($b);$q=count($c); $a=array(); while($i<$p && $j<$q){ if($b[$i]<=$c[$j]){ $a[$k]=$b[$i]; $i++; }else{ $a[$k]=$c[$j]; $j++; } $k++; } if($i==$p){ $xxx = slice_array($c,$j,$q); }else{ $xxx = slice_array($b,$i,$p); } return merge_array($a,$xxx); }
[edit] Groovy
def mergeSort(list){ if( list.size() <= 1) return list center = list.size() / 2 left = list[0..center] right = list[center..list.size()] merge(mergeSort(left), mergeSort(right)) } def merge(left, right){ sorted = [] while(left.size() > 0 || right.size() > 0) if(left.get(0) <= right.get(0)){ sorted << left }else{ sorted << right } sorted = sorted + left + right }
[edit] Eiffel
class APPLICATION create make feature -- Initialization make is -- do end feature -- Algorithm mergesort(a:ARRAY[INTEGER]; l,r:INTEGER) is -- 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) is -- 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]
