二路归并排序实现

用python实现

def Merge(A,low,mid,high): i=low j=mid+1 T=[] while i<=mid and j<=high: if A[i]<A[j]: T.append(A[i]) i=i+1 else: T.append(A[j]) j=j+1 while i<=mid: T.append(A[i]) i=i+1 while j<=high: T.append(A[j]) j=j+1 A[low:high+1]=T[:] def MergeSort(A,low,high): if low<high: mid=int((low+high)/2) MergeSort(A,low,mid) MergeSort(A,mid+1,high) Merge(A,low,mid,high) def main(): A=[2,3,1,4,3,3,7,8,4,6,3,1,5,2,4,7,8,0,9,4,6,7] MergeSort(A,0,len(A)-1) print('MergeSort:',A) if __name__=='__main__': main()

用C++实现

#pragma once #include<iostream> #include<vector> using namespace std; void Merge(int A[], int low, int mid, int high) { int i = low; int j = mid + 1; vector<int> T; while (i <= mid && j <= high) { if (A[i] > A[j]) { T.push_back(A[j++]); } else { T.push_back(A[i++]); } } while (i <= mid) { T.push_back(A[i++]); } while (j <= high) { T.push_back(A[j++]); } int k = low; for (auto e : T) { A[k++] = e; } } void MergeSort(int A[], int low, int high) { if (low < high) { int mid = (low + high) / 2; MergeSort(A, low, mid); MergeSort(A, mid + 1, high); Merge(A, low, mid, high); } }