归并排序

自顶向下归并

• 过程

  
  
  自顶向下归并.jpg
• 代码

  void sort(vector<int> &vec) {
      if (vec.size() <= 1)
          return;
      if (temp.empty())
          vec2.resize(vec.size());
      sort(vec, 0, vec.size()-1);
  }
  
  void sort(vector<int> &vec, int lo, int hi)  {
      if (lo >= hi)
          return;
      int mid = lo + (hi-lo)/2;
      sort(vec, lo, mid);
      sort(vec, mid+1, hi);
      merge(vec, lo, mid, hi);
  }

  void merge(vector<int> vec, int lo, int mid, int hi)  {
      int i = lo, j = mid + 1;
      for (int k = lo; k <= hi; k++)
          temp[k] = vec[k];

      int k = lo;
      while(i <= mid && j <= hi)  {
          if (temp[i] <= temp[j])
              vec[k++] = temp[i++]
          else
              vec[k++] = temp[j++];
      }
      if (i <= mid)              // [lo, mid]有剩余
          while(i <= mid)
              vec[k++] = temp[i++];
      else                        // [mid+1, hi]有剩余
          while(j <= hi)
              vec[k++] = temp[j++];
  }

自底向上归并

• 过程

  
  
  自底向上归并.jpg
• 代码