Merge sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] Introduction
- The fundamental operation in this algorithm is merging two sorted lists. Because the lists are sorted, this can be done in one pass through the input, if the output is put in a third list. The basic merging algorithm takes two input arrays a and b, an output array c, and three counters, aptr, bptr, and cptr, which are initially set to the beginning of their respective arrays. The smaller of a[aptr] and b[bptr] is copied to the next entry in c, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the other list is copied to c.
[edit] Pseudocode
Merge sort
Assumption: Here we present the merge sort algorithm as a recursive algorithm. Procedure sort(int , int) divides the file and calls the sort procedure to recursively sort the sub files. The procedure mergeArray( int int , int ) merges a pair of sorted array. We consider a[] to be an array containing n elements.
Void sort(int first, int last)
{
Step 1: If file size is one then return;
Otherwise calculate mid as mid=(first+last)/2;
Step 2: Recursively sort the two sub array i) [first to mid]
ii) and [mid+1 to last] by calling
sort(first,mid);
sort(mid+1,last);
Step 3: Merge the two array i) [first to mid] ii) and [mid+1
to last] by calling
mergeArray(first,mid,last);
Step 4: Stop
}
void mergeArray(int first,int mid,int last)
{
Step 1: Consider an auxiliary array as aux[] and set the to the
Beginning of every array.
Step 2: Repeat step 3 While both the array [ i) [first to mid] ii) and [mid+1 to last]] has elements.
Step 3: if (first array value < second array value)
[Pointed to by the corresponding pointer]
Then assign first array value to aux.
Else assign second array value to aux.
Step 4: Copy remaining value from first or second array. [ if any]
Step 5: Copy backs all the elements from aux to the original value.
Step 6: Stop.
}
[edit] C Code by Chris Taylor
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
[edit] Another code (faster)by Chris Taylor
#include <stdlib.h>
void m_sort(int* tab, int* tab_cpy, const size_t sz)
{
size_t n, i, j, mid;
/* swap & divide (recursive) */
mid = sz/2;
if (mid > 1) m_sort(tab_cpy, tab, mid);
if (sz-mid > 1) m_sort(tab_cpy+mid, tab+mid, sz-mid);
/* merge */
int* tab_cpy2 = tab_cpy+mid;
for (n=0, i=0, j=0; i<mid && j<sz-mid; n++)
tab[n] = (tab_cpy[i] < tab_cpy2[j]) ? tab_cpy[i++] : tab_cpy2[j++];
while (i<mid)
tab[n++] = tab_cpy[i++];
while (j<sz-mid)
tab[n++] = tab_cpy2[j++];
}
void merge_sort (int* tab, size_t sz)
{
int* tab_cpy = malloc(sz * sizeof *tab);
/* copy */
size_t i;
for (i=0; i<sz; i++)
tab_cpy[i] = tab[i];
/* sort */
m_sort(tab, tab_cpy, sz);
free(tab_cpy);
}
[edit] C++ Code
[edit] Loop (using STL algorithm)
template <typename Type> inline
void Merge(Type *pF, Type *pL) // loop
{
const int nSIZE = pL-pF;
Type *pSrc = pF;
Type *pBuf = new Type[nSIZE];
int nBeg, nMid, nEnd;
for (nMid=1; nMid < nSIZE; nMid<<=1) {
for (nBeg=0; nBeg < nSIZE; nBeg += (nMid<<1)) {
nEnd = nBeg + (nMid<<1);
nEnd = nEnd > nSIZE ? nSIZE : nEnd;
if (nBeg+nMid >= nSIZE) {
copy(pSrc+nBeg, pSrc+nSIZE, pBuf+nBeg);
break;
}
int a = nBeg;
int b = nBeg + nMid;
for (int i=nBeg-1; ++i<nEnd;) {
if ((pSrc[a]<=pSrc[b] && a < nBeg+nMid) || b==nEnd) {
pBuf[i]=pSrc[a++];
} else {
pBuf[i]=pSrc[b++];
}
}
}
iter_swap(&pSrc, &pBuf); // swap address (not value)
}
if (pBuf==pF) {
copy(pSrc, pSrc+nSIZE, pF);
iter_swap(&pSrc, &pBuf);
}
delete [] pBuf;
}
[edit] Recursive
template <typename Type> inline
void Merge_Rec(Type *pF, Type *pL) // recursive
{
if (pL-pF > 1) {
Type *pBuf = new Type[pL-pF];
Type *pMid = pF + (pL-pF)/2;
Merge_Rec(pF, pMid); // [pF, pMid)
Merge_Rec(pMid, pL); // [pMid, pL)
Type *pLt, *pRt;
for (pLt=pMid; --pLt>=pF;) { pBuf[pLt-pF] = *pLt; }
for (pRt=pMid-1; ++pRt<=pL-1;) { pBuf[(pMid-pRt) + (pL-pF) - 1] = *pRt; }
pLt++, pRt--;
for (Type *pI=pF; pI<pL; pI++) {
*pI = (pBuf[pLt-pF] < pBuf[pRt-pF]) ? pBuf[pLt++ - pF] : pBuf[pRt-- -pF];
}
delete [] pBuf;
}
}
[edit] PHP Code by Julian Schneider
function mergesort($array){
if (count($array)<= 1){
return $array;
}else{
$indexanzahl = count($array);
$halfeindex = (int)($indexanzahl/2);
$halfeindex2 = $indexanzahl-$halfeindex;
$right_array = array_splice($array, $halfeindex);
$left_array = array_slice($array, count($left_array), $halfeindex2);
return merge(mergesort($left_array), mergesort($right_array) );
}
}
function merge($left_array, $right_array){
$_sortiert = array();
while(count($left_array) != 0 && count($right_array) != 0){
if ($left_array[0] <= $right_array[0]){
array_push($_sortiert, $left_array[0]);
array_shift($left_array);
}else{
array_push($_sortiert, $right_array[0]);
array_shift($right_array);
}
}
while(count($left_array) != 0){
array_push($_sortiert, $left_array[0]);
array_shift($left_array);
}
while(count($right_array) != 0){
array_push($_sortiert, $right_array[0]);
array_shift($right_array);
}
return $_sortiert;
}
[edit] C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sorting
{
class Program
{
static void Main(string[] args)
{
int[] arr = new int[10];
Random r = new Random();
for (int i = 0; i < arr.Length; i++)
{
arr[i] = r.Next(1, 20);
}
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
arr = MergeSort(arr);
Console.WriteLine("After sorting");
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
Console.ReadKey();
}
// implementing merge sort
public static int[] MergeSort(int[] a)
{
int[] left, right, result;
if (a.Length <= 1) return a;
int len = a.Length;
int middle = (int)(len / 2) - 1;
left = new int [middle+1];
right = new int [len-(middle+1)];
for (int i = 0; i <= middle; i++)
left[i] = a[i];
for (int j = middle + 1; j < len; j++)
right[j - (middle+1)] = a[j];
left = MergeSort(left);
right = MergeSort(right);
if (left[left.Length - 1] > right[0])
result = Merge(left, right);
else
{
result = new int[left.Length + right.Length];
result = Append(left, right);
}
return result;
}
public static int[] Merge(int[] x, int[] y)
{
int[] result = new int[x.Length + y.Length];
int i = 0;
bool xflag = false, yflag = false;
while (x.Length > 0 && y.Length > 0)
{
if(x[0] <= y[0])
{
result[i] = x[0];
i++;
if (x.Length == 1)
{
xflag = true;
break;
}
x = RemoveFirst(x);
}
else
{
result[i] = y[0];
i++;
if (y.Length == 1)
{
yflag = true;
break;
}
y = RemoveFirst(y);
}
}
if (!xflag)
{
for (int j = 0; j < x.Length; j++)
{
result[i] = x[j];
i++;
}
}
else
{
for (int j = 0; j < y.Length; j++)
{
result[i] = y[j];
i++;
}
}
return result;
}
public static int[] Append(int[] x, int[] y)
{
int [] result = new int [x.Length+y.Length];
int len = result.Length;
int i=0;
while (i < len)
{
for (int j = 0; j < x.Length; j++)
{
result[i] = x[j];
i++;
}
for (int j = 0; j < y.Length; j++)
{
result[i] = y[j];
i++;
}
}
return result;
}
public static int[] RemoveFirst(int[] x)
{
int [] temp = new int[x.Length - 1];
int j = 0;
for (int i = 1; i < x.Length; i++)
{
temp[j] = x[i];
j++;
}
return temp;
}
}
}
[edit] C# 3.5
public static class ListMergeSort<T> where T : IComparable
{
public static List<T> Sort(List<T> list)
{
if (list.Count > 1)
{
var mid = list.Count / 2;
list = Merage(Sort(list.GetRange(0, mid)), Sort(list.GetRange(mid, list.Count - mid)));
}
return list;
}
private static List<T> Merage(List<T> Left, List<T> Right)
{
List<T> Out = new List<T>();
while (Left.Count > 0 && Right.Count > 0)
{
Out.Add(Left.First().CompareTo(Right.First()) <= 0 ? Left.First() : Right.First());
(Left.First().CompareTo(Right.First()) <= 0 ? Left : Right).RemoveAt(0);
}
return Out.Concat(Left.Count == 0 ? Right : Left).ToList();
}
}
[edit] Java Code
public int[] Two_Way_Merge_Sort(int[] A, int[] B) {
int[] C = new int[A.length + B.length];
int k = 0;
int i = 0;
int j = 0;
while(i < A.length && j < B.length) {
if (A[i] < B[j])
C[k++] = A[i++];
else
C[k++] = B[j++];
}
while (i < A.length)
C[k++] = A[i++];
while (j < B.length)
C[k++] = B[j++];
return C;
}
}
[edit] VB Code
This section needs your Code!
[edit] Perl Code
sub mergesort
{
my ($a, $l, $r) = @_;
if ($l < $r)
{
my $m = floor(($l+$r)/2);
mergesort($a, $l, $m);
mergesort($a, $m+1, $r);
merge($a, $l, $m, $r);
}
}
sub merge
{
my ($a, $l, $m, $r) = @_;
my $i = $l;
my $j = $m + 1;
my $k = $l;
my @b = ();
while($i <= $m && $j <= $r)
{
if ($$a[$i] <= $$a[$j])
{
$b[$k] = $$a[$i];
$i++;
}
else
{
$b[$k] = $$a[$j];
$j++;
}
$k++;
}
if ($i > $m)
{
for (my $h = $j; $h <= $r; $h++)
{
$b[$k + $h - $j] = $$a[$h];
}
}
else
{
for (my $h = $i; $h <= $m; $h++)
{
$b[$k + $h - $i] = $$a[$h];
}
}
for(my $h = $l; $h <= $r; $h++)
{
$$a[$h] = $b[$h];
}
}
[edit] Prolog Code
merge([], Liste, Liste).
merge(Liste, [], Liste).
merge([Kopf1|Liste1], [Kopf2|Liste2], [Kopf1|Liste3]):- Kopf1 =< Kopf2, merge(Liste1, [Kopf2|Liste2], Liste3).
merge(Liste1, [Kopf2|Liste2], [Kopf2|Liste3]):- merge(Liste1, Liste2, Liste3).
dividelist([], [], []).
dividelist([Element], [Element], []).
dividelist([Element, Element2|Rest1], [Element|Rest2], [Element2|Rest3]):- dividelist(Rest1, Rest2, Rest3).
mergesort([], []).
mergesort([Element], [Element]).
mergesort(Liste, SortierteListe):- dividelist(Liste, Liste1, Liste2),
mergesort(Liste1, SortierteListe1),
mergesort(Liste2, SortierteListe2),
merge(SortierteListe1,SortierteListe2,SortierteListe), !.
[edit] Python Code
def mergeSort(l):
if(len(l)<=1): return l[:]
middle = len(l)/2
return merge(mergeSort(l[:middle]), mergeSort(l[middle:]))
def merge(left,right):
if left == [] or right == [] :
return left + right
elif left[0] <= right[0] :
return left[:1] + merge(left[1:], right)
else :
return right[:1] + merge(left, right[1:])
[edit] Ruby Code
def merge(left, right)
out = []
until left.empty? or right.empty?
out << (left.first <= right.first ? left.shift : right.shift)
end
out.concat left + right
end
def merge_sort(ary)
return ary if ary.size <= 1
mid = ary.size / 2
merge(merge_sort(ary[0...mid]), merge_sort(ary[mid..-1]))
end
