2
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <time.h>

void DISPLAY(int*, int);

int* MERGE(int*, int,  int* , int,  int* , int ); 
int* MERGESORT(int* , int ); 



int main()
{

    int* array = NULL;
    array = (int*) malloc(7 * sizeof(int) );
    
    array[0] = 10;
    array[1] = 9;
    array[2] = 8;
    array[3] = 57;
    array[4] = 6;
    array[5] = 5;
    array[6] = 24;
    
    printf("\nOriginal array: \n");
    DISPLAY(array, 7);
                
    array = MERGESORT(array, 7);
                
    printf("\n\nResulting array: \n");
    DISPLAY(array, 7);
}

void DISPLAY(int* array, int size)
{
    int i;                                          
    for(i = 0; i < size; i++){                  
        printf("%d ", array[i]);
    }
}


int* MERGESORT(int *array, int size) {
    if(size < 2) 
        return array; 

    int mid = size / 2;             
    int rightsize = size-mid;   

    int* L = (int*) malloc(mid * sizeof(int));         
    int* R = (int*) malloc((size-mid) * sizeof(int));  
    int i;
    for(i = 0; i < mid; i++) 
        L[i] = array[i];                            
    for(i = mid; i < size; i++) 
        R[i-mid] = array[i];                    

    L = MERGESORT(L, mid);                           
    R = MERGESORT(R, size-mid);                     
    array = MERGE(array, size, L, mid, R, rightsize);       
    free(L);                                        
    free(R);                                    
    
    return array;
}


int* MERGE(int *array, int size, int *L, int leftsize,int *R, int rightsize) {
    int i, j, k;
    
    i = 0; 
    j = 0; 
    k = 0;

    while(i < leftsize && j < rightsize)    
    {                   
        if(L[i] < R[j])                     
        {
            array[k] = L[i];                
            i++;                            
        }
        else{                           
            array[k] = R[j];            
            j++;                        
        }
        k++;                        
    }
    while(i < leftsize)                 
    {
        array[k] = L[i];                    
        i++;                                
        k++;                                    
    }
    while(j < rightsize)
    {
        array[k] = L[j];                
        j++;                                
        k++;                            
    }
    
    printf("\nUpdated array: \n");                       
    DISPLAY(array, size);
    return array;
}

Hello, I have a problem when I try to perform merge sorting in an array. Some items in the array are printing weird. Every time the arrays get updated, the value gets printed out, but it doesn't work at specific inputs.

When I input small numbers (like 1-2 digits), then the array gets sorted normally.

Sample run of program sorting incorrectly: https://i.sstatic.net/OLg0b.png

3
  • 1
    Take this as an opportunity to learn how to use a debugger to step through your code statement by statement while monitoring variables and their values. Commented Dec 17, 2020 at 12:04
  • Hint: in a = malloc(n * sizeof *a), you can only reference a[0] through a[n-1]. Commented Dec 17, 2020 at 12:07
  • In malloc((size-mid) * sizeof(int)) why not use rightsize instead of size - mid? Same when you call MERGESORT(R, size-mid). I also recommend you start to use unsigned types for sizes and indexes, preferably size_t. Commented Dec 17, 2020 at 12:30

2 Answers 2

1
while(j < rightsize)
    {
        array[k] = L[j];                
        j++;                                
        k++;                            
    }

should be

while(j < rightsize)
        {
            array[k] = R[j];                
            j++;                                
            k++;                            
        }

Umm, sorry for wasting time on such a simple mistake.

Sign up to request clarification or add additional context in comments.

Comments

0

Consider.

int* R = (int*) malloc((size-mid) * sizeof(int)); 

(which ought to be written int *R = malloc((size - mid) * sizeof *R);)

What is the highest valid index in that array? Trying to read from (or write to) R[n] for n > size - mid - 1 invokes undefined behavior.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.