归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin

下面是代码，这里面的Merge1函数和之前的Merge函数稍微有一点不同，Merge1不需要将最终的结果放到A函数。

归并排序算法是稳定，但是由于它反复的来回复制导致在内部排序中不常用，通常情况下内部排序是不会用到归并排序的，归并排序经常用在外部排序当中。

外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

https://baike.baidu.com/item/%E5%A4%96%E9%83%A8%E6%8E%92%E5%BA%8F/10595890?fr=aladdin

内部排序

内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。

https://baike.baidu.com/item/%E5%86%85%E9%83%A8%E6%8E%92%E5%BA%8F

下面详细看代码：

#include <iostream>
using namespace std; 
#include <stdlib.h>/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void Merge_pass(int A[], int tempA[], int N, int length);
void Merge1(int A[], int tmpA[], int L, int R, int RightEnd);
void Merge_Sort(int A[], int N);void Merge_pass(int A[], int tempA[], int N, int length)
{int i ;for ( i = 0; i <= N-2*length; i+=2*length){Merge1(A, tempA, i, i+length, i+2*length-1);}if (i+length < N)Merge1(A, tempA, i, i+length, N-1);else{for (int j = i; j < N; j++)tempA[j] = A[j];	}}void Merge1(int A[], int TmpA[], int L, int R, int rightEnd)
{int leftEnd = R-1;int tmp = L;while(L <= leftEnd && R <= rightEnd){if (A[L] <= A[R]){TmpA[tmp++] = A[L++];}else{TmpA[tmp++] = A[R++];}}while(L <= leftEnd){TmpA[tmp++] = A[L++];}while( R <= rightEnd){TmpA[tmp++] = A[R++];}
}void Merge_Sort(int A[], int N)
{int length = 1;int *TmpA;TmpA = (int *)malloc(N);if (TmpA != NULL){while(length < N){Merge_pass(A, TmpA, N, length);	length *= 2;Merge_pass(TmpA, A, N, length);length *= 2;}free(TmpA);}else{cout << "空间不足error" << endl;	}
}int main(int argc, char** argv) 
{int A[10] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};for (int i = 0; i < 10; i++){cout << A[i] << " "; }cout << endl;Merge_Sort(A, 10);for (int i = 0; i < 10; i++){cout << A[i] << " "; }cout << endl;return 0;
}