Что случилось с моей (с указателем) слиянием?

Question

Нет ошибок, просто не сортировать список. Он работал, когда я напрямую использовал индексы вместо указателей. Я чувствую, что мне не хватает чего-то о том, как должен вести себя указатель .... Правильно ли я полагаю, что указатели передаются по значению (скопированному) в рекурсивные вызовы или я их испортил?

#include<iostream> 

using namespace std; 

void merge(int *start, int *pivot, int *end) { 
    const int n = start - end; 
    int ret[n]; 
    int i; 
    for (i=0; i<n; ++i) { 
     if (*start < *pivot) { 
      ret[i] = *(start++); 
     } 
     else { 
      ret[i] = *(pivot++); 
     } 
    } 
    for (i=0;i<n;++i) { 
     start[i] = ret[i]; 
    } 
} 

void sort1(int* start,int* end) { 
    int n = end - start; 
    if (n <= 1) { 
     return; 
    } 
    int* pivot = &start[n/2]; 
    sort1(start,pivot); 
    sort1(pivot,end); 
    merge(start,pivot,end); 
} 

int main() { 
    int x[] = {1,3,6,2,4,5}; 
    sort1(x,x+6); 
    int i; 
    for (i=0; i<6; ++i) { 
     cout << x[i] << endl; 
    } 
} 

Мой выходной ток 1 1 3 3 1 1

Answer 1

Ваш базовый случай в sort1 является обратно; более конкретно, вычисление n.

Answer 2

Я думаю, что ваше слияние виновато. На двух подматрицах нет ограничений на тестирование, поэтому, как только вы достигнете конца одного массива, вы будете брать значения из другого (которые уже скопированы).

Это нормально, чтобы разделить код для слияния в трех петель следующим образом:

int *a1 = start; 
int *a2 = pivot; 
int *r = &ret[0]; 

// Copy smallest from each sub-array 
while(a1 != pivot && a2 != end) { 
    if(*a1 < *a2) *r++ = *a1++; 
    else *r++ = *a2++; 
} 

// Copy remaining values from first sub-array 
while(a1 != pivot) *r++ = *a1++; 

// Copy remaining values from second sub-array 
while(a2 != end) *r++ = *a2++; 

Answer 3

слияния() повторное использование начало и середина, часть кода наступающей оба указателя, в то время как другой код ожидая, что они будут исходные значения. Также n должен быть конечным (не начальным). Примечание. Использование стека для ret [] будет проблемой для большого массива. new и delete можно использовать вместо _alloca или второй массив, выделенный в main и переданный как параметр. Убрано пример:

#include <iostream> 
// using _alloca since VS doesn't support variable length array 
#include <malloc.h> 

using namespace std; 

void merge(int *start, int *middle, int *end) { 
    const int n = (int)(end - start); 
    int *ret = (int *) _alloca(n * sizeof(int)); 
    int *left = start; 
    int *right = middle; 
    int i; 
    for (i=0; i < n; ++i) { 
     if (right >= end || left < middle && *left <= *right) { 
      ret[i] = *(left++); 
     } else { 
      ret[i] = *(right++); 
     } 
    } 
    for (i=0;i<n;++i) { 
     start[i] = ret[i]; 
    } 
} 

void sort1(int* start, int* end) { 
    int n = (int)(end - start); 
    if (n <= 1) { 
     return; 
    } 
    int* middle = &start[n/2]; 
    sort1(start,middle); 
    sort1(middle,end); 
    merge(start,middle,end); 
} 

int main() { 
    int x[] = {1,3,6,2,4,5}; 
    sort1(x,x+6); 
    int i; 
    for (i=0; i<6; ++i) { 
     cout << x[i] << endl; 
    } 
    return 0; 
}