# 归并排序

归并排序一般是将数组分成两部分，分别进行排序，然后将排好序的两部分合并在一起

# 基本思想

用递归的思想将数组分成两部分，分别进行排序，然后将排好序的两部分合并在一起

# 归并的实现


//举例说明两个有序数组的合并
// int arr=[12, 16, 24, 33, 45, 56, 60]
// int arr1=[7, 10, 21, 24, 37]
// int arr2=[] //用来存储合并后的数组
// 每次循环比较两个数组的第一个元素，将较小的元素放到新的数组中，然后将较小元素所在的数组的下标加1，继续比较，直到其中一个数组的元素全部放到新的数组中，然后将另一个数组的剩余元素全部放到新的数组中

// 举例说明
// 第一趟 12和7比较 7小 放到新的数组中 7所在的数组下标加1 得到 arr2=[7]

// 第二趟 12和10比较 10小 放到新的数组中 10所在的数组下标加1 得到 arr2=[7, 10]

// 第三趟 12和21比较 12小 放到新的数组中 12所在的数组下标加1 得到 arr2=[7, 10, 12]

// ...

//最后一趟将arr 或 arr1中剩余的元素全部放到arr2中

//代码实现

void merge(int *arr, int *arr1, int *arr2, int length, int length1) {
  //i用来记录arr的下标，j用来记录arr1的下标，k用来记录arr2的下标

    int i = 0, j = 0, k = 0;
    //循环比较arr和arr1的元素，将较小的元素放到arr2中
    int min=length<length1?length:length1;
    for(int m=0;m<min;m++){
        if(arr[i]<arr1[j]){
            arr2[k++]=arr[i++];
        }else{
            arr2[k++]=arr1[j++];
        }
    }

    while(i<length){
        arr2[k++]=arr[i++];
    }

    while(j<length1){
        arr2[k++]=arr1[j++];
    }
 
 }

# 归并排序的实现


int arr[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};

int *B = (int *) malloc(sizeof(int) * 10);

//一般采用递归的思想，将数组分成两部分，分别进行排序，然后将排好序的两部分合并在一起
//low 为数组的第一个元素 high为数组的最后一个元素 mid为数组的中间元素
void Merge(int A[], int low, int x, int high) {
    int i, j, k;
    // 将A中的数据复制到B中
    for (k = low; k <= high; ++k) {
        B[k] = A[k];
    }
    // 将B中的数据按照顺序复制到A中
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {
        if (B[i] <= B[j]) {
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    // 将B中剩余的数据复制到A中
    while (i <= mid) {
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

void MergeSort(int A[], int low, int high) {
    if (low < high) {
      // 将数组分成两部分，分别进行排序
        int mid = (low + high) / 2;
        //递归的处理左侧数组
        MergeSort(A, low, mid);
        //递归的处理右侧数组
        MergeSort(A, mid + 1, high);
        //将排好序的两部分合并在一起
        Merge(A, low, mid, high);
    }
}

# 算法分析

2路归并的树是一个倒立的二叉树

# 时间复杂度

归并的时间复杂度为O(n)

n个元素进行2路归并排序需要log2n次

算法的时间复杂度为O(nlog2n)

# 空间复杂度

O(n) 用于辅助的数组长度为n

← 堆排序