# 归并排序的C#,java,js,python,ruby实现

## C 实现 Merge sort

```// 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.
// Never 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);
}
```

## C++

```//! \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);
}
```

```//! \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;
}
```

```#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)     // Recursive 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;
}
```

## 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;
}
```

## Erlang

```merge_sort(List) when length(List) =< 1 -> List;
merge_sort(List) ->
{Left, Right} = lists:split(length(List) div 2, List),
lists:merge(merge_sort(Left), merge_sort(Right)).
```

## Java 归并排序

```public int[] mergeSort(int array[])  {
if(array.length > 1)    {
int elementsInA1 = array.length/2;
int elementsInA2 = array.length - elementsInA1;
int arr1[] = new int[elementsInA1];
int arr2[] = new int[elementsInA2];

for(int i = 0; i < elementsInA1; i++)
arr1[i] = array[i];

for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
arr2[i - elementsInA1] = array[i];

arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);

int i = 0, j = 0, k = 0;

while(arr1.length != j && arr2.length != k) {
if(arr1[j] <= arr2[k]) {
array[i] = arr1[j];
i++;
j++;
} else {
array[i] = arr2[k];
i++;
k++;
}
}

while(arr1.length != j) {
array[i] = arr1[j];
i++;
j++;
}
while(arr2.length != k) {
array[i] = arr2[k];
i++;
k++;
}
}
return array;
}
```

## 归并排序的JavaScript实现

```function merge_sort(arr) {
var l = arr.length, m = Math.floor(l/2);
if (l <= 1) return arr;
return merge(merge_sort(arr.slice(0, m)), merge_sort(arr.slice(m)));
}

function merge(left,right) {
var result = [];
var ll = left.length, rl = right.length;
while (ll > 0 && rl > 0) {
if (left[0] <= right[0]) {
result.push(left.shift());
ll--;
} else {
result.push(right.shift());
rl--;
}
}
if (ll > 0) {
result.push.apply(result, left);
} else if (rl > 0) {
result.push.apply(result, right);
}
return result;
}
```

## PHP实现归并排序

```function merge_sort(&\$arrayToSort)
{
if (sizeof(\$arrayToSort) <= 1)
return \$arrayToSort;

// split our input array into two halves
// left...
\$leftFrag = array_slice(\$arrayToSort, 0, (int)(count(\$arrayToSort)/2));
// right...
\$rightFrag = array_slice(\$arrayToSort, (int)(count(\$arrayToSort)/2));

// RECURSION
// split the two halves into their respective halves...
\$leftFrag = merge_sort(\$leftFrag);
\$rightFrag = merge_sort(\$rightFrag);

\$returnArray = merge(\$leftFrag, \$rightFrag);

return \$returnArray;
}

function merge(&\$lF, &\$rF)
{
\$result = array();

// while both arrays have something in them
while (count(\$lF)>0 && count(\$rF)>0) {
if (\$lF[0] <= \$rF[0]) {
array_push(\$result, array_shift(\$lF));
}
else {
array_push(\$result, array_shift(\$rF));
}
}

// did not see this in the pseudo code,
// but it became necessary as one of the arrays
// can become empty before the other
array_splice(\$result, count(\$result), 0, \$lF);
array_splice(\$result, count(\$result), 0, \$rF);

return \$result;
}
```

## 归并排序的Python实现

```def mergesort(arr):
if len(arr) == 1:
return arr

m = len(arr) / 2
l = mergesort(arr[:m])
r = mergesort(arr[m:])

if not len(l) or not len(r):
return l or r

result = []
i = j = 0
while (len(result) < len(r)+len(l)):
if l[i] < r[j]:
result.append(l[i])
i += 1
else:
result.append(r[j])
j += 1
if i == len(l) or j == len(r):
result.extend(l[i:] or r[j:])
break

return result
```

## 归并排序的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
```

## 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
```

## 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
}
```

0人收藏

0

0