lundi 25 janvier 2021

What is wrong with this merge sort algorithm?

Can someone please tell what is wrong with this piece of code? This code is to sort a set of elements in an array using merge sort.

#include<iostream>

void merge(int arr[], int left, int mid, int right){
    int left_ptr = left;
    int right_ptr = mid + 1;
    int size = right - left + 1;       
    int temp[size];
    int k = left;

    while (left_ptr <= mid && right_ptr <= right)
    {
        if(arr[left_ptr] <= arr[right_ptr]){
            temp[k] = arr[left_ptr];
            left_ptr++;
            k++;
        }
        else{
            temp[k] = arr[right_ptr];
            right_ptr++;
            k++;
        }
        
    }

    while (left_ptr <= mid)
    {
        temp[k] = arr[left_ptr];
        left_ptr++;
        k++;
    }

    while (right_ptr <= right)
    {
        temp[k] = arr[right_ptr];
        right_ptr++;
        k++;
    }
    
    for (int i = left_ptr; i < k; i++)
    {
        arr[i] = temp[i];
    }
    
}

void mergeSort(int arr[], int left, int right){
    int mid;
    if (left < right)
    {
        mid = (right + left)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
}
int main(){
    int arr[] = {45,8,9,7,4,58,2,34,2,58}; 
    std::cout << arr << std::endl; 
    int size = sizeof(arr)/sizeof(int);
    mergeSort(arr, 0, size - 1);
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "    ";
    }

    std::cout << std::endl;
    
}

I double checked it with many online codes and I see no error... What do you think went wrong? I tried to implement this using an array in-place (something like quick-sort).

Aucun commentaire:

Enregistrer un commentaire