Background

  归并排序的实现

Description

  请完成下述归并代码框架后提交，只需完成注释中的要求，无需输入输出

#include "MergeSort.h"
    
// 通过归并排序对int队列nums中的[left, right]区间进行升序排序
// @param
// nums: 完整的待排序队列，最终排序的结果应存放在nums中
// left: 当前排序区间的左端点
// right: 当前排序区间的右端点
void MergeSort::merge_sort_aux(std::vector<int> &nums, int left, int right)
{
    //请在这里完成你的代码
}

Samples

  提供一组样例用于自测

6
2 6 7 2 1 8 

1 2 2 6 7 8

Limits

  $N\leq10^6$，其中$N$为待排序的元素个数

附 MergeSort.h

#pragma once
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <functional>

using namespace std;

class MySort {
public:
	virtual void mysort(std::vector<int>& nums) = 0;
};

class MergeSort : public MySort
{
public:
  // 通过归并排序对int队列nums中的[left, right]区间进行升序排序
  // @param
  // nums: 完整的待排序队列，最终排序的结果应存放在nums中
  // left: 当前排序区间的左端点
  // right: 当前排序区间的右端点
  void merge_sort_aux(std::vector<int> &nums, int left, int right);
  
  void mysort(std::vector<int> &nums)
  {
    int n = nums.size();
    merge_sort_aux(nums, 0, n - 1);
  }
};