-1

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
trincot
  • 317,000
  • 35
  • 244
  • 286
Circuit_Breaker0.7
  • 125
  • 1
  • 5
  • 2
    Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Andreas Wenzel Jan 15 '22 at 08:10
  • I tested your program on two different platforms, and I got a segmentation fault/access violation (i.e. a crash) in both cases. I suggest that you run your code in a debugger, to determine where the segmentation fault is occurring. If you are using the "gcc" or "clang" compiler, compiling with `-fsanitize=address` will provide additional useful information. – Andreas Wenzel Jan 15 '22 at 08:22
  • 1
    It seems that you use some software development environment setup that hides from you that the program crashes. It is very bad for learning C++ as crashes will be frequent on that road. – Öö Tiib Jan 15 '22 at 08:23

1 Answers1

1

The problem is with k:

As you use k as index in temp, you should not let k start at l, but at 0. Your code will access memory outside of the range of temp, and that gives undefined results or a segmentation fault. For the same reasons, in the final loop, where you copy from temp, you cannot use the same index value for temp and for x. You'll want to copy temp[0] to x[l], temp[1] to x[l+1], ...etc.

So change:

k = l;

to:

k = 0;

And change:

for (i = l; i < k; i++)
   x[i] = temp[i];

to:

for (i = 0; i < k; i++)
   x[l + i] = temp[i];
trincot
  • 317,000
  • 35
  • 244
  • 286