function mergeSort(arr){// 採用自上而下的遞歸方法 var len = arr.length; if(len <2){ return arr; } var middle =Math.floor(len /2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); }
function merge(left, right) { var result =[];
while (left.length&& right.length){ if(left[0]<= right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } }
def merge(left,right): result =[] while left and right: if left[0]<= right[0]: result.append(left.pop(0)) else: result.append(right.pop(0)); while left: result.append(left.pop(0)) while right: result.append(right.pop(0)); return result
Go
實例
func mergeSort(arr []int)[]int{ length :=len(arr) if length < 2{ return arr } middle := length /2 left := arr[0:middle] right := arr[middle:] return merge(mergeSort(left), mergeSort(right)) }
func merge(left []int, right []int)[]int{ var result []int forlen(left)!=0 && len(right)!=0{ if left[0] <= right[0]{ result = append(result, left[0]) left = left[1:] }else{ result = append(result, right[0]) right = right[1:] } }
forlen(left)!=0{ result = append(result, left[0]) left = left[1:] }
forlen(right)!=0{ result = append(result, right[0]) right = right[1:] }
int min(int x,int y){ return x < y ? x : y; } void merge_sort(int arr[],int len){ int*a = arr; int*b =(int*)malloc(len *sizeof(int)); int seg, start; for(seg =1; seg < len; seg += seg){ for(start =0; start < len; start += seg *2){ int low = start, mid = min(start + seg, len), high = min(start + seg *2, len); int k = low; int start1 = low, end1 = mid; int start2= mid, end2 = high; while(start1 < end1 && start2 < end2) b[k++]= a[start1]< a[start2]? a[start1++]: a[start2++]; while(start1 < end1) b[k++]= a[start1++]; while(start2 < end2) b[k++]= a[start2++]; } int*temp = a; a = b; b = temp; } if(a != arr){ int i; for(i =0; i < len; i++) b[i]= a[i]; b = a; } free(b); }
遞歸版:
實例
void merge_sort_recursive(int arr[], int reg[], int start, int end){ if(start >= end) return; int len = end - start, mid =(len >>1)+ start; int start1 = start, end1 = mid; int start2 = mid +1, end2 = end; merge_sort_recursive(arr, reg, start1, end1); merge_sort_recursive(arr, reg, start2, end2); int k = start; while(start1 <= end1 && start2 <= end2) reg[k++]= arr[start1]< arr[start2]? arr[start1++]: arr[start2++]; while(start1 <= end1) reg[k++]= arr[start1++]; while(start2 <= end2) reg[k++]= arr[start2++]; for(k = start; k <= end; k++) arr[k]= reg[k]; }
void merge_sort(int arr[], constint len){ int reg[len]; merge_sort_recursive(arr, reg, 0, len -1); }
C++
迭代版:
實例
template<typename T>// 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能 void merge_sort(T arr[], int len){ T *a = arr; T *b =new T[len]; for(int seg =1; seg < len; seg += seg){ for(int start =0; start < len; start += seg + seg){ int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while(start1 < end1 && start2 < end2) b[k++]= a[start1]< a[start2]? a[start1++]: a[start2++]; while(start1 < end1) b[k++]= a[start1++]; while(start2 < end2) b[k++]= a[start2++]; } T *temp = a; a = b; b = temp; } if(a != arr){ for(int i =0; i < len; i++) b[i]= a[i]; b = a; } delete[] b; }
遞歸版:
實例
void Merge(vector<int>&Array, int front, int mid, int end){ // preconditions: // Array[front...mid] is sorted // Array[mid+1 ... end] is sorted // Copy Array[front ... mid] to LeftSubArray // Copy Array[mid+1 ... end] to RightSubArray vector<int> LeftSubArray(Array.begin()+ front, Array.begin()+ mid +1); vector<int> RightSubArray(Array.begin()+ mid +1, Array.begin()+ end +1); int idxLeft =0, idxRight =0; LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max()); RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max()); // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i] for(int i = front; i <= end; i++){ if(LeftSubArray[idxLeft]< RightSubArray[idxRight]){ Array[i]= LeftSubArray[idxLeft]; idxLeft++; }else{ Array[i]= RightSubArray[idxRight]; idxRight++; } } }
void MergeSort(vector<int>&Array, int front, int end){ if(front >= end) return; int mid =(front + end)/2; MergeSort(Array, front, mid); MergeSort(Array, mid +1, end); Merge(Array, front, mid, end); }
C#
實例
publicstatic List<int> sort(List<int> lst){ if(lst.Count<=1) return lst; int mid = lst.Count/2; List<int> left =new List<int>();// 定義左側List List<int> right =new List<int>();// 定義右側List // 以下兩個循環把 lst 分為左右兩個 List for(int i =0; i < mid; i++) left.Add(lst[i]); for(int j = mid; j < lst.Count; j++) right.Add(lst[j]); left = sort(left); right = sort(right); return merge(left, right); } /// <summary> /// 合併兩個已經排好序的List /// </summary> /// <param name="left">左側List</param> /// <param name="right">右側List</param> /// <returns></returns> static List<int> merge(List<int> left, List<int> right){ List<int> temp =new List<int>(); while(left.Count>0&& right.Count>0){ if(left[0]<= right[0]){ temp.Add(left[0]); left.RemoveAt(0); }else{ temp.Add(right[0]); right.RemoveAt(0); } } if(left.Count>0){ for(int i =0; i < left.Count; i++) temp.Add(left[i]); } if(right.Count>0){ for(int i =0; i < right.Count; i++) temp.Add(right[i]); } return temp; }
Ruby
實例
def merge list return list if list.size<2
pivot = list.size/2
# Merge lambda{|left, right| final = [] until left.empty? or right.empty? final <<if left.first< right.first; left.shiftelse right.shiftend end final + left + right }.call merge(list[0...pivot]), merge(list[pivot..-1]) end