Сортировка слиянием относиться к классу алгоритмов “разделяй и властвуй”. Является устойчивой. Сложность алгоритма O(n*log(n)), требует выделение дополнительной памяти. Алгоритм изобретен Джоном фон Нейманом в 1945г. Ниже приведен код реализации.
void merge(int*src,int left,int middle,int right) { int* aux = new int[right-left]; int i=left; int j=middle+1; int index=0; for(int k=left;k<=right;k++) { if(i>middle) { aux[index]=src[j]; j++; }else if(j>right) { aux[index]=src[i]; i++; }else if(src[i]<src[j]) { aux[index]=src[i]; i++; }else { aux[index]=src[j]; j++; } index++; } for(int k=0;k<=right-left;k++) src[k+left]=aux[k]; } void MergeSort(int* src,int left,int right) { if(left>=right) return; int middle = (right+left)/2; MergeSort(src,left,middle); MergeSort(src,middle+1,right); merge(src,left,middle,right); }
Оставить комментарий