C ++ сортировка слиянием Упражнение: сортировка коллекции целых чисел с использованием сортировки слиянием

С ++ Сортировка: упражнение 10 с решением

Напишите программу на C ++ для сортировки коллекции целых чисел, используя сортировку Merge.

Пример решения :

Код C ++:

#include<iostream>
using namespace std;
void Merge(int* A,int,int,int);
void Merge_Sort(int* A,int p,int r);
int main()
{   
  int a[] = {125, 0, 695, 3, -256, -5, 214, 44, 55};
  int len = 9;
  cout << "Original numbers:\n";
  for(int i=0; i<len; i++) {
        cout << a[i] << " ";
    }
   
    Merge_Sort(a,0,len-1);
    cout << "\nSorted numbers:\n";
    for(int i=0; i<len; i++) {
        cout << a[i] << " ";
    }
    return 0;
}
void Merge(int* arr,int p,int q,int r) {
    int n1=q-p+1;
    int n2=r-q;
    int L[n1+1];
    int R[n2+1];
    for(int i=0; i<n1; i++) L[i]=arr[p+i];
    for(int j=0; j<n2; j++) R[j]=arr[q+1+j];
    int i=0;
    int j=0;
    int n=0;
    while(i!=n1 && j!=n2) {
        if(L[i]>R[j]) {
            arr[p+n]=R[j];
            j++;
        } else {
            arr[p+n]=L[i];
            i++;
        }
        n++;
    }
    while(j!=n2) {
        arr[p+n]=R[j];
        j++;
        n++;
    }
    while(i!=n1) {
        arr[p+n]=L[i];
        i++;
        n++;
    }
}
void Merge_Sort(int* arr,int p,int r) {
    if(r>p) {
        int q;
        q=(p+r)/2;
        Merge_Sort(arr,p,q);
        Merge_Sort(arr,q+1,r);
        Merge(arr,p,q,r);
    }
}

Пример вывода:

 Оригинальные номера:
125 0 695 3 -256 -5 214 44 55 
Сортированные номера:
-256 -5 0 3 44 55 125 214 695 

Блок - схема:

Редактор кода C ++:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на C ++ для сортировки массива элементов с использованием алгоритма сортировки Insertion.
Далее: Напишите программу на C ++, чтобы отсортировать коллекцию целых чисел, используя сортировку Pancake.