5)連結ソート

マージソートは、分割征服(Split征服)メソッドを使用するアルゴリズムです.
結果は,O(N*logN)の時間的複雑さを有する高速ソートと同様であった.
しかし、急速なソートとは異なり、最悪の場合もO(N*logN)を保障しなければならない.
次の質問を見てください.
以下の数字を昇順に並べ替えるプログラムを作成してください.
( 7, 6, 5, 8, 3, 5, 9, 1 )

#include <iostream>
using namespace std;

int number = 8;
int sorted[8];

void merge(int a[], int m, int middle, int n){
	int i = m;
	int j = middle + 1;
	int k = m;
	while (i <= middle && j <= n) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	if (i > middle) {
		for (int t = j; t <= n; t++)
		{
			sorted[k] = a[t];
			k++;
		}
	}
	else
	{
		for (int t = i; t <= middle; t++)
		{
			sorted[k] = a[t];
			k++;
		}
	}
	for (int t = m; t <= n; t++)
	{
		a[t] = sorted[t];
	}
}

void mergesort(int a[], int m, int n) {
	if (m < n) {
		int middle = (m+n) / 2;
		mergesort(a, m, middle);
		mergesort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

int main(void) {
	
	int array[8] = { 7, 6, 5, 8, 3, 5, 9, 1 };
	mergesort(array, 0, number - 1);
	for (int t = 0; t < number; t++)
	{
		cout << array[t];
	}
	
}

マージソートは、2つの小さな問題を別々に計算し、最後にマージする方法です.
解答に示すように,8つの配列空間が存在する場合はmergesortで半分に分ける.
[ 7, 6, 5, 8, 3, 5, 9, 1 ]
上の列を半分に開く.
[7 ,6, 5, 8]     [3, 5, 9, 1]
また分ける.
[6, 7]  [5, 8]  [3, 5]  [1, 9]
次に、上の小さな数字と大きな数字を比較して、順序を変更します.
[6, 7]  [5, 8]
次に、上記の数値をソートし、1つずつ集計します.
[5, 6, 7, 8]
集計ソートを実施する場合、
つまり、ソートに使用する配列をグローバル変数として宣言する必要があります.
関数で配列を宣言する場合は、配列を1つずつ宣言する必要があります.
これは、メモリリソースの浪費が非常に大きいためです.
デフォルトでは、
必要性から、メモリの利用効率が低いという問題がある.
マージソートは、高速ソートよりも遅いが、O(N*logN)を保証する効率的なアルゴリズムである.