在不使用临时数组的情况下合并归并排序

Question

我正在尝试实现合并排序，但不知何故已经卡了一天。

[抱歉粘贴了大量代码，但没有它就无法做到]

执行：

归并排序 - 函数

int mergeSort(int arr[], int low, int high)
{
        int half = (low + high) / 2 ;    /* FInd the middle element */ 
        if (low < high)
        {
            if (high - low == 1)             /* If only one element, return */
                return;
            mergeSort(arr,low,half);    /* Sort First Half */
            mergeSort(arr,half, high); /* Sort Second Half */
            merge(arr,low,half,high);  /* Merge */
        }
      return SUCCESS;
}

合并步骤 - 合并功能

int merge(int arr[], int low, int half, int high)
{
    int i = 0, j =0, k = 0, l = 0, temp;    /* Initialize indices */

    for(i = low, j = half;i < half && j < high; i++,j++)    /* Swap in the array itself if the elements are out of order */
    {
        if (arr[i] > arr[j])
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }

    i = 0,j = low;  /* Compare and copy the elements in a global arrray C */
    for(k = 0; k < SIZE && i < low && j < high; k++)
    {
        if (arr[i] < arr[j])
        {
            c[k] = arr[i];
            i++;
        }
        else
        {
            c[k] = arr[j];
            j++;
        }
    }

    if (i < j) /* Copy remaining elements to the end of the array C */
    {
        for (l = i; l < low; l++)
        {
            c[k++] = arr[l];
        }
    }
    else
    {
        for (l = j; l < high; l++)
        {
            c[k++] = arr[l];
        }
    }

输出

8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
4 --> 5 --> 8 --> 9 --> 
1 --> 2 --> 4 --> 5 --> 8 --> 9 --> /* Sorting when left is sorted but right is in the process ? */
4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 1 --> 2 --> 
1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 
1 --> 2 --> 6 --> 7 --> 4 --> 5 --> 8 --> 9 --> 

问题描述

我没有使用任何本地数组来存储数组的元素。相反，如果元素乱序，则交换元素，然后通过比较将其复制到全局数组中 示例：如果我有数组

{ 9, 8, 4, 5, 2, 1, 7, 6}

然后，首先{8,9}将被排序，然后{4,5}将被排序，然后在复制程序时{8,4}进行比较，依此类推。发生以下递归调用

mergeSort(0,8) -> mergeSort(0,4) , mergeSort(4,8), merge(0,4,8)
mergeSort(0,4) -> mergeSort(0,2) , mergeSort(2,4), merge(0,2,4)
mergeSort(0,2) -> 1 element calls
and so on.

当{4,5,8,9}排序时调用合并，并调用右边merge(4,5,6)我有以下数组

{4,5,8,9,1,2,7,6}

所以，算法试图排序{4,5,8,9}，{1,2}何时{1,2}不是这个子问题的一部分，即我想要{1,2}和'{6,7}成为{1,2,6,7}，然后将这两者结合起来。

我如何克服这个问题？我被困了这么多小时。

非常感谢

Answer 1

就地合并排序很少（如果曾经使用过），因为就地合并操作虽然可能，但与使用额外缓冲区的明显版本相比相当复杂。

尽管很少建议，但可以通过交替原始缓冲区和额外缓冲区之间的合并来获得有效的版本，以最大限度地减少移动次数。必须注意在递归调用中进行偶数次合并。这可以通过对极少数元素（或替代排序）实现真正的就地合并来解决。