Реализация сортировки слияния

Question

Я новичок в C++ и пытаюсь разработать код для сортировки слияния. Я тестировал его с помощью массива выборок размером 5, но ответ, который выдает код, неверен. Я не могу понять, что происходит не так. Вот мой код:

#include <iostream> 
#include <cstring> 
#include <sstream> 
#include <fstream> 
#include <iomanip> 
using namespace std; 
void merge(int, int, int, int*); 
void merge_sort(int low, int high, int* p){ 
    int pivot; 
    static int i(1); 
    if (high>low) 
    { 
     cout << "calling merge_sort: "<<i<<endl; i++; 
     pivot = low + ((high - low)/2); 
     cout << pivot << endl; 
     merge_sort(low, pivot, p); 
     merge_sort(pivot+1, high, p); 
     merge(low, pivot, high, p); 

    } 
} 
void merge(int l, int pi, int h,int* arr) 
{ 
      int start = l; 
     int mid = pi+1; 
     while((start<=pi)&&(mid <=h)){ 
      if (arr[start] > arr[mid]) 
      { 
       int temp = arr[mid]; 
       arr[mid] = arr[start]; 
       arr[start] = temp; 
       mid++; 
      } 
      else 
       start++; 
    } 
} 
int main() 
{ 
    int a[] = {2, 42, 3, 7, 1}; 
    merge_sort(0, 4, a); 
    for (int i = 0; i<=4 ; i++) 
     cout << a[i] << endl; 
    return (0); 

} 

Выход следующим образом:

calling merge_sort: 1 
2 
calling merge_sort: 2 
1 
calling merge_sort: 3 
0 
calling merge_sort: 4 
3 
1 
3 
7 
2 
42 

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

Любая помощь очень ценится при сортировке этой проблемы.

Answer 1

Эти строки, кажется мне неправильным:

int temp = arr[mid-1]; // It should be [mid] here 
arr[mid] = arr[start]; // Or [mid-1] here 
arr[start] = temp; 

Для замены двух индексов, что два должны совпадать.

Answer 2

Логика в вашем слиянии неверна. На этапе слияния вы знаете, что у вас есть 2 раздела отсортированных номеров. Когда вы сравниваете и меняете arr[start] и arr[mid], вы разбиваете сортировку верхнего набора чисел, если arr[start] > arr[mid+1]. Пример показывает проблемы с кодом, как 2 будет оставлен в неправильном месте:

4 6 8 | 1 3 5 -> 1 6 8 | 4 3 5 
^  ^  ^  ^

Для того, чтобы держать 2 секции отсортированным вы должны вставить arr[start] в нужном месте в верхнем наборе чисел, сделает сложность хуже, чем O(n lg n). Именно по этой причине используется второй массив.

Есть метод, который использует меньшие массивы, чем оригинал для слияния, они имеют свои накладные расходы, но не ставят под угрозу сложность (или правильность). Если вы хотите, чтобы O(n lg n) на месте сортировки, то быстроходная или гипсортская дорога.

Answer 3

Вот реализация сортировки слиянием для целочисленных массивов:

void merge_sort (int array[], int size) 
{ 
    int temp[size]; 
    int mid, i; 
    if (size < 2) { 
     return; 
    } 
    else { 
     mid = size/2; 
     merge_sort(array, mid); 
     merge_sort(array + mid, size - mid); 
     merge (array, mid, array + mid, size - mid, temp); 
     for (i = 0; i < size; i++) { 
      array[i] = temp[i]; 
     } 
    } 
} 

int merge (int list1[ ] , int size1 , int list2[ ] , int size2 , int list3[ ]) 
{ 
    int i1, i2, i3; 
    if (size1+size2 > size) { 
     return false; 
    } 
    i1 = 0; i2 = 0; i3 = 0; 
    /* while both lists are non-empty */ 
    while (i1 < size1 && i2 < size2) { 
     if (list1[i1] < list2[i2]) { 
      list3[i3++] = list1[i1++]; 
     } 
     else { 
      list3[i3++] = list2[i2++]; 
     } 
    } 
    while (i1 < size1) { 
     /* copy remainder of list1 */ 
     list3[i3++] = list1[i1++]; 
    } 
    while (i2 < size2) { 
     /* copy remainder of list2 */ 
     list3[i3++] = list2[i2++]; 
    } 
    return true; 
} 

И если вы хотите использовать его для других типов, которые можно использовать в C++ шаблонов, как это:

template <class T> 
T* merge_sort(T arr[], int n) 
{ 
    if(n < 2){return arr;} 
    int mid = n/2; 
    T *arr1 = merge_sort<T>(arr,mid); 
    T *arr2 = merge_sort<T>(arr+mid,n-mid); 
    return merge(arr1, mid, arr2, n-mid); 
} 

template <class T> 
T* merge(T arr1[], int size1, T arr2[], int size2) 
{ 
    int i = 0,j = 0; 

    T* out_array = new T[size1+size2]; 

    while((i < size1) && (j < size2)) 
    { 
     if(arr1[i] >= arr2[j]) 
     { 
      out_array[i+j] = arr2[j]; 
      ++j; 
     } 
     else 
     { 
      out_array[i+j] = arr1[i]; 
      ++i; 
     } 
    } 
    while(i < size1) 
    { 
     //copy the reminder 
     out_array[i+j] = arr1[i]; 
     i++; 
    } 
    while(j < size2) 
    { 
     out_array[i+j] = arr2[j]; 
     j++; 
    } 
    return out_array; 
} 

Но с:

#include <iostream> 
using namespace std; 

int main() { 
    int a[] = {2, 42, 3, 7, 1}; 
    int *a2 = merge_sort(a,5); 
    for (int i = 0; i<= 4 ; ++i) 
     cout << a2[i] << endl; 
    return (0); 
} 

Выход:

1 
2 
3 
7 
42 

Надеюсь, я немного помог.

Answer 4

Это один работал ОТЛИЧНО в CodeBlocks (компилятор используется: MinGW)

#include <iostream> 

using namespace std; 

void merge(int*,int*,int,int,int); 
void mergesort(int *a, int*b, int low, int high) 
{ 
int pivot; 
if(low<high) 
{ 
    pivot=(low+high)/2; 
    mergesort(a,b,low,pivot); 
    mergesort(a,b,pivot+1,high); 
    merge(a,b,low,pivot,high); 
} 
} 
void merge(int *a, int *b, int low, int pivot, int high) 
{ 
int h,i,j,k; 
h=low; 
i=low; 
j=pivot+1; 

while((h<=pivot)&&(j<=high)) 
{ 
    if(a[h]<=a[j]) 
    { 
     b[i]=a[h]; 
     h++; 
    } 
    else 
    { 
     b[i]=a[j]; 
     j++; 
    } 
    i++; 
} 
if(h>pivot) 
{ 
    for(k=j; k<=high; k++) 
    { 
     b[i]=a[k]; 
     i++; 
    } 
} 
else 
{ 
    for(k=h; k<=pivot; k++) 
    { 
     b[i]=a[k]; 
     i++; 
    } 
} 
for(k=low; k<=high; k++) a[k]=b[k]; 
} 

int main() 
{ 
int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24}; 
int num; 

num = sizeof(a)/sizeof(int); 

int b[num]; 

mergesort(a,b,0,num-1); 

for(int i=0; i<num; i++) 
    cout<<a[i]<<" "; 
cout<<endl; 
}