歸并排序 算法

算法思路

1. 将一個數列不斷拆分為子序列，直到隻剩下0或者1個元素
2. 再将子序列按順序合并為原來數列的大小，完成排序

代碼實作

//合并兩個有序數組
vector<int> merge_two_sort(vector<int> &arr1, vector<int> &arr2) {
  vector<int> result;
  int i = 0, j = 0;
  while(i < arr1.size() && j < arr2.size()) {
    if (arr1[i] <= arr2[j]) {
      result.push_back(arr1[i]);
      i++;
    } else {
      result.push_back(arr2[j]);
      j++;
    }
  }
  if (i == arr1.size()) {
    while(j < arr2.size()) {
      result.push_back(arr2[j]);
      j++;
    }
  } else {
    while(i < arr1.size()) {
      result.push_back(arr1[i]);
      i++;
    }
  }
  return result;
}

vector<int> merge_sort(vector<int> &arr) {
  if (arr.size() < 2) {
    return arr;
  }
  int mid = arr.size() / 2;
  //拆分為兩個子數組
  vector<int> arr1(arr.begin(), arr.begin() + mid); 
  vector<int> arr2(arr.begin() + mid, arr.end());
  
  //最終遞歸拆分，為大小小于2的子數組，再進行兩個數組的合并操作
  return merge_two_sort(merge_sort(arr1), merge_sort(arr2));
}      

算法分析