C++实现
class MergeSort {
public:
void merge(int* A, int l, int mid, int r)
{
// start merger
int tmp[r-l+1];
int idx = 0;
int idx_l = l;
int idx_r = mid;
while(idx_l < mid && idx_r < r+1){
if(A[idx_l] < A[idx_r]){
tmp[idx++] = A[idx_l++];
}else{
tmp[idx++] = A[idx_r++];
}
}
if(idx_l==mid){
while(idx_r < r+1){
tmp[idx++] = A[idx_r++];
}
}else{
while(idx_l < mid){
tmp[idx++] = A[idx_l++];
}
}
idx = 0;
while(idx < r-l+1){
A[l+idx] = tmp[idx];
idx++;
}
}
void process(int* A, int l, int r)
{
if(l==r){
return;
}
int mid = (r+l)/2;
process(A, l, mid);
process(A, mid+1, r);
merge(A, l, mid+1, r);
}
int* mergeSort(int* A, int n) {
// write code here
// if(1==n){
// return A;
// }
process(A, 0, n-1);
return A;
}
};
python 实现
# -*- coding:utf-8 -*-
class MergeSort:
def mergeSort(self, A, n):
# write code here
if 1==n:
return A
else:
mid = n / 2
A1 = self.mergeSort(A[:mid], mid)
A2 = self.mergeSort(A[mid:], n-mid)
result = [0]*(n)
for i in xrange(n):
if A1 and A2:
if A1[0] < A2[0]:
result[i] = A1.pop(0)
else:
result[i] = A2.pop(0)
elif not A1:
result[i] = A2.pop(0)
else:
result[i] = A1.pop(0)
return result
网友评论