My Merge Sort program is not working as it should

  algorithm, c++, mergesort, sorting

This method works good for small arrays (9 elements), but any more than that and I don’t get the desired output. It just shows the unsorted array but does not display the sorted array as I have coded it below.

#include<iostream>

void merge(int x[], int l, int m, int h){
    int i = l;
    int j = m+1;
    int k = l;
    int temp[h-l+1];
    while(i<=m && j<=h){
        if( x[i] < x[j] ){
            temp[k] = x[i];
            i++;
        }
        else{
            temp[k] = x[j];
            j++;
        }
        k++;
    }
    while(i<=m){
        temp[k] = x[i];
        i++;
        k++;
    }
    while(j<=h){
        temp[k] = x[j];
        j++;
        k++;
    }
    for(i=l; i<k; i++)
        x[i] = temp[i];
}

void mergeSort(int x[], int l, int h){
    if (l<h){
        int mid = (l+h)/2;
        mergeSort(x, l, mid);
        mergeSort(x, mid+1, h);
        merge(x, l, mid, h);
    }
}

void Display(int x[], int m){
    for(int i=0; i<m;i++){
        std::cout << x[i] << " ";
        if (!(i%10) && i !=0)  std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main(){
    int m, i=0;
    int x[] = {3, 1, 56, 12 , 11, 19, 80, 100, 0};
    m = sizeof(x)/sizeof(x[0]);
    std::cout << "Unsorted:n";
    Display(x, m);
    mergeSort(x, 0, m-1);
    std::cout << "nSorted: n";
    Display(x, m);
    return 0;
}

The output I get is:

Unsorted:
3 1 56 12 11 19 80 100 0

The correct output:

Unsorted:
3 1 56 12 11 19 80 100 0

Sorted:
0 1 3 11 12 19 56 80 100

Source: Windows Questions C++

LEAVE A COMMENT