关于归并排序的一些BUG

Question

#include <iostream>
using namespace std;

 /**
   * 归并排序
   * 简介:将两个（或两个以上）"有序"表合并成一个新的有序表 即把待排序序列分为若干个子序列，
   *     每个子序列是有序的。然后再把有序子序列合并为整体有序序列
   * 时间复杂度为O(nlogn)
   * 稳定排序方式
   * @param nums 待排序数组
    @return 输出有序数组
   **/
    void merge(int arr[], int start, int mid,int end)
    { 
        mid = (start + end) / 2;
        int mi = mid + 1;
        int k = 0;
        int  *tmp = new int[end+1];
        
        while (start <= mid && mi <= end)
        {
            if (arr[start] <= arr[mid])
            {
                tmp[k++] = arr[start++];
            }
            else 
            {
                tmp[k++] = arr[mi++];
            }
           
        }
        //若其中一个没排完，把剩下的元素放进tmp
        while (start <= mid) 
            tmp[k++] = arr[start++];
        while (mi<= end)  
            tmp[k++] = arr[mi++];

        for (int i = start, j = 0; i <= end; i++, j++) {
            arr[i] = tmp[j];
        }
        delete []tmp;
        tmp = nullptr;
    }

    void merge_sort(int arr[], int start, int end)//递归
    {
        
        if (arr==nullptr||end == 0 || ( end-start)<=1)
        {
            return;
        }
       
        if (start < end)
        {
            int mid = (start + end) / 2;
            int middle = mid + 1;
           
            merge_sort(arr, start, mid);
            merge_sort(arr, middle , end);
            merge(arr, start, mid, end);//将两个有序子数组合并操作
        }
      
       
    }
   

int main()
{
    int a[] = {3,2,9,20,8,15,18};
    int length = sizeof(a) / sizeof(a[0]);
    merge_sort(a, 0, length-1);
    for (int i = 0; i < length; i++)
        cout << a[i] << " ";
}

输出的时候发现排序不成功，有没有大佬帮忙看一下是哪里的问题？

Answer 1

#include <iostream>
using namespace std;
    void merge(int arr[], int start, int mid,int end)
    { 
        mid = (start + end) / 2;
        int mi = mid + 1;
        int k = 0;
        int  *tmp = new int[end-start+1];
        int s = start;//下面start++自增，改变start的值，s为start备份 
        while (start <= mid && mi <= end)
        {
            if (arr[start] <= arr[mi])//这里mid应该改为mi 
            {
                tmp[k++] = arr[start++];
            }
            else 
            {
                tmp[k++] = arr[mi++];
            }
           
        }
        //若其中一个没排完，把剩下的元素放进tmp
        while (start <= mid) 
            tmp[k++] = arr[start++];
        while (mi<= end)  
            tmp[k++] = arr[mi++];
 
        for (int i = s, j = 0; i <= end; i++, j++) {//用start的备份s，start已自增 
            arr[i] = tmp[j];
            cout << tmp[j] << " ";
        }
        cout<<endl;
        delete []tmp;
        tmp = nullptr;
    }
 
    void merge_sort(int arr[], int start, int end)//递归
    {
        
        if (arr==nullptr||end == 0 || ( end-start)==0)
        {
            return;
        }
        if(end-start == 1){//少了一步 
        	if(arr[start]>arr[end]){
        		int temp = arr[start];
        		arr[start] = arr[end];
        		arr[end] = temp;
			}
			return;
		}
       
        if (start < end)
        {
            int mid = (start + end) / 2;
            int middle = mid + 1;
           
            merge_sort(arr, start, mid);
            merge_sort(arr, middle , end);
            merge(arr, start, mid, end);//将两个有序子数组合并操作
        }
      
       
    }
   
 
int main()
{
    int a[] = {3,2,9,20,8,15,18};
    int length = sizeof(a) / sizeof(a[0]);
    merge_sort(a, 0, length-1);
    for (int i = 0; i < length; i++)
        cout << a[i] << " ";
}