Последовательная сортировка слияния в C

Question

Я пытаюсь переписать рекурсивный Merge Сортировать как

void MergeSort(int* data, int size){ 
    int half=size/2; 
    if (size > 1) { 
    MergeSort(data, half); 
    MergeSort(data+half, half); 
    Merge(data, size); 
    } 
} 

, в котором

void Merge(int* data, int size){ 
    int cnt; 
    int cntLow=0; 
    int half=size/2; 
    int cntHigh=half; 
    int* sorted; 

    sorted = (int*) malloc(size*sizeof(int)); 

    for (cnt=0; cnt<size; cnt++){ 
    if (cntLow == half) 
     sorted[cnt] = data[cntHigh++]; 
    else if (cntHigh == size) 
     sorted[cnt] = data[cntLow++]; 
    else if (data[cntLow] <= data[cntHigh]) 
     sorted[cnt] = data[cntLow++]; 
    else 
     sorted[cnt] = data[cntHigh++]; 
    } 

    for (cnt=0; cnt<size; cnt++) 
    data[cnt] = sorted[cnt]; 

    free(sorted); 
} 

к нерекурсивен вызову. Поэтому я написал функцию

void MergeSort_NonRecursive(int* data, int size){ 
    int i; 
    int j; 

    for (i=size; i>0; i=i/2){ 
     for (j=0; j<i; j++){ 
      Merge(data + j*size/i, size/i); 
     } 
    } 
} 

, который, по-видимому, работает для последовательностей размером $ 2^n $. Однако, когда я запускаю его в последовательности размером, отличной от $ 2^n $, он не сортируется правильно, поэтому в какой-то точке MergeSort_NonRecursive мой код должен быть ошибочным.

Итак, где я сделал неправильно (в MergeSort_NonRecursive)? (также, мне нужно использовать функцию Merge).

Заранее спасибо.

Answer 1

Поскольку размер int, размер/2 усекает ваш коэффициент.

например. если размер = 4, размер/2 = 2. если размер = 5, размер/2 = 2. если размер = 6, размер/2 = 3.

Итак, для размера 5 требуется первая репликация MergeSort вызов оператору по размеру/2 элементам (т. е. первые 3), и второй вызов для работы с оставшимися 2 элементами.

Можно сказать, например.

int half = size/2; //size = 5: half = 2 
int rest = size - half; //rest = 3 

так:

void MergeSort(int* data, int size){ 
    int half=size/2; 
    int rest = size-half; 
    if (size > 1) { 
    MergeSort(data, half); 
    MergeSort(data+half, rest); //changed this line 
    Merge(data, size); 
    } 
} 

Edit:

Похоже, вы немного изменили вопрос, после того, как я отправил. Общая идея по-прежнему стоит: когда вы делите int на другой int, фактор усекается.

В вашем MergeSort_NonRecursive вы делите int s в ряде мест, например. i=i/2, j*size/i, size/i. Обратите внимание на значения, которые вы получите.