//
// Merge Sort
// Created by Win10 on 2023/4/7.
//

#ifndef C_DATA_STRUCTURE_MERGE_SORT_H
#define C_DATA_STRUCTURE_MERGE_SORT_H


#include <algorithm>

template<typename T>
//归并排序迭代写法
void merge_sort(T a[], int len) {
  T *a_ = new T[len];
  for (int seg = 1; seg < len; seg += seg) {
    for (int beg = 0; beg < len; beg += seg + seg) {
      int low = beg, mid = std::min(beg + seg, len), high = std::min(beg + seg + seg, len);
      int i = low, j = mid, k = low;
      while (i < mid && j < high) a_[k++] = a[i] > a[j] ? a[j++] : a[i++];
      while (i < mid) a_[k++] = a[i++];
      while (j < high) a_[k++] = a[j++];
      for (k = beg; k < high; ++k) a[k] = a_[k];
    }
  }
  delete[] a_;
}

#endif //C_DATA_STRUCTURE_MERGE_SORT_H