Thread: Problem with Merge sort algorithm

Hello,

sounds weird but i can't seem to get this merge sort to work. running through gdb though; appreciate any eyes.

Code:

/**
 *Filename: mergeSort.c
 *Usage: This implements merge sort algorithm to sort and array of numbers.
 */


#include <stdio.h>
#include <stdlib.h>



int merge(int A[], int p, int q, int r) {

    int n1 = q - p;
    int n2 = r - q;
    
    int L[n1], R[n2];    
    int i, j, k;

    for( i = 0; i < n1; i++ )
	L[i] = A[p + i];

    for( j = 0; j < n2; j++)
	R[j] = A[q + j];


    //this part is not really necessary since array holds
    // only subarray elements.
    
    for( k = p, i = 0, j = 0 ; k < r && i < n1 && j < n2; k++) {

	if(L[i] <= R[j]){
    A[k] = L[i++];
          
        } else {
           A[k] = R[j++];
        }
    }


    return 0;
}
  


int mergeSort(int A[],int start, int end) {

     if((end - start) <= 1)
	return;
 
     int q = (start + end) /2;
     mergeSort(A, start, q);
     mergeSort(A, q+1, end);
     merge(A, start, q, end);
  

    return 0;
}

/**
 *New implementation of mergesort algorithm.
 */
void print_list(int A[], int len) {
   
      int i;
      //prints any array of numbers.
      printf("[ ");
      for( i = 0; i < len; i++){
         printf(" %d , ", A[i]);
      }
      
      printf("]\n");
}

 
 /*the mergesort algorithm on some sample input.
 */
int main(void){

    int array[] = { 19, 4, 19, 3, 19, 34, 18, 834, 3239, 1, 0, 23, 983, 83, 13, 07, 5, -2, -44};

    //This prints the unsorted array.
    printf("\nTest - unsorted list: ");
    print_list(array, 19);

    //Sorted array.
    mergeSort(array,0, 19);
    printf("\n Test - sorted list: ");
    print_list(array,19);
     return 0;
}

The two merge sort calls should be mergeSort(A, start, q); then mergeSort(a, q, end); (and not q+1) . The for / if statements in merge need to be changed so that the loop handles the case when the end of L[] or R[] is reached before reaching the end of the other half array.

Originally Posted by rcgldr

The for / if statements in merge need to be changed so that the loop handles the case when the end of L[] or R[] is reached before reaching the end of the other half array.

Forgot to post the fix:

Code:

/* ... */
    for(i = 0, j = 0, k = p ; k < r ; k++) {
        if(j >= n2 || i < n1 && L[i] <= R[j])
            A[k] = L[i++];
        else
            A[k] = R[j++];
    }