Thread: Not able to find mistake in Merge Sort

Hello guys,I have this Merge Sort Program. I am not able to understand and when I tried to understand with debugging ,it does not give output too. Can someone help me out with explanation of this recursive msort and merge function? I am really sorry to bother but I want to learn this sorting technique. I understand manual but I don't understand through this code.

Code:

main()
{
int i,low,high,n,a[10];
printf("how many elements");
scanf("%d",&n);
printf("Enter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i);
low=0;
high=n-1;
msort(a,low,high);
printf("The sorted array is ");
for(i=0;i<n;i++)
printf("%d",a[i]);
getch();
}
msort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
msort(a,low,mid);
msort(a,mid+1,high);
merge(a,low,mid,high);
}
}
merge(int a[],int low ,int mid ,int high)
{
int h,k,i,j,b[10];
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i=i+1;
}
}
else
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}

Hie Yes I noticed my mistake later and fixed it so the progamming is running. No. I did not steal. It's there in Book. But,I am not able to understand code work .If I pass values then as per my understanding msort(a,low,mid) will run until the condition is false.
Then msort(a,mid+1,high) will run until the condition is false.
Then merge(a,low,mid,high) funtion will be called.
While loop will work until condition is false.
Then if else part will as per conditions.
Then last for part will work and we will get result .
Program ends here.
But,I found some video wherein they show after these steps once again program runs many times.
The codes are different though but recursion and functions remain same. So,I am confused where am I going wrong ?

Originally Posted by Salem

Gee, where did you steal that from?

It doesn't even compile.
foo.c:14:16: error: expected ‘]’ before ‘)’ token
scanf("%d",&a[i);

The indentation is non-existent -> Indent style - Wikipedia

Code:

#include <stdio.h>

void msort(int a[], int low, int high);
void merge(int a[], int low, int mid, int high);

int main()
{
  int i, low, high, n, a[10];
  printf("how many elements");
  scanf("%d", &n);
  printf("Enter the elements");
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  low = 0;
  high = n - 1;
  msort(a, low, high);
  printf("The sorted array is ");
  for (i = 0; i < n; i++)
    printf("%d\n", a[i]);
  return 0;
}

void msort(int a[], int low, int high)
{
  int mid;
  if (low < high) {
    mid = (low + high) / 2;
    msort(a, low, mid);
    msort(a, mid + 1, high);
    merge(a, low, mid, high);
  }
}

void merge(int a[], int low, int mid, int high)
{
  int h, k, i, j, b[10];
  h = low;
  i = low;
  j = mid + 1;
  while ((h <= mid) && (j <= high)) {
    if (a[h] <= a[j]) {
      b[i] = a[h];
      h = h + 1;
    } else {
      b[i] = a[j];
      j = j + 1;
    }
    i = i + 1;
  }
  if (h > mid) {
    for (k = j; k <= high; k++) {
      b[i] = a[k];
      i = i + 1;
    }
  } else
    for (k = h; k <= mid; k++) {
      b[i] = a[k];
      i = i + 1;
    }
  for (k = low; k <= high; k++) {
    a[k] = b[k];
  }
}

> it does not give output too.
Yes it does, if you fix the printf's

Code:

$ gcc -Wall foo.c
$ ./a.out 
how many elements5
Enter the elements3 6 1 2 8
The sorted array is 1
2
3
6
8

Yes I have Turno C7 .Debugger is not working properly so I am doing it manually.

Originally Posted by Salem

I think you need a better book to be honest, not to mention a better compiler (lemme guess, you're using TurboC).

The whole point about software is you can change it however you want whenever you want.

So if you don't understand something, you can either run it in a debugger and follow the code path, or throw in a few printf statements at what seem like interesting points in the code.

Code:

#include <stdio.h>

void msort(int a[], int low, int high,int recursiveDepth);
void merge(int a[], int low, int mid, int high);

int main()
{
  int i, low, high, n, a[10];
  printf("how many elements");
  scanf("%d", &n);
  printf("Enter the elements");
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  low = 0;
  high = n - 1;
  msort(a, low, high,0);
  printf("The sorted array is\n");
  for (i = 0; i < n; i++)
    printf("%d\n", a[i]);
  return 0;
}

void msort(int a[], int low, int high,int recursiveDepth)
{
  int mid;
  if (low < high) {
    mid = (low + high) / 2;
    printf("%*s: Depth=%d, low=%d, high=%d, mid=%d\n", 
           recursiveDepth*2, "", 
           recursiveDepth, low, high, mid );
    msort(a, low, mid,recursiveDepth+1);
    msort(a, mid + 1, high,recursiveDepth+1);
    merge(a, low, mid, high);
  }
}


...
$ gcc foo.c
$ ./a.out 
how many elements7
Enter the elements1 3 5 7 6 4 2
: Depth=0, low=0, high=6, mid=3
  : Depth=1, low=0, high=3, mid=1
    : Depth=2, low=0, high=1, mid=0
    : Depth=2, low=2, high=3, mid=2
  : Depth=1, low=4, high=6, mid=5
    : Depth=2, low=4, high=5, mid=4
The sorted array is
1
2
3
4
5
6
7

I liked printf idea. And I tried to put this in between in lines and get each value output.I used gdb online debugger. Funny thing is final result remains correct but the value of each variable is different everytime I run the program. There is no accuracy.