Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Information about my code:

I am following this MIT OCW algorithms course. The first lecture described insertion sort and merge sort. I implemented merge sort in C.

The algorithm is structured as a function called from the main function. The array to be sorted is allocated dynamically in the main function but can also be statically allocated.

What I am looking for:

I am looking whether the 2 functions can be optimized without changing the algorithm(merge sort), whether it follows the best-practices of programming in C and does it have proper readability factor?

Please Note:

I will keep posting edited code if additional suggestions are made. Please fell free to review any and all of the versions.

My code

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

#define SORTING_ALGO_CALL merge_sort

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This for and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int i, k;
    int temp, j = temp = length/2;
    for (i = k = 0; (i < temp && j < length); k++){
        ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    if(i >= temp){
        while(j < length){
            ans[k++] = arr[j++];
        }
    }
    else{
        while(i < temp){
            ans[k++] = arr[i++];
        }
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < length; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        merge_sort(&arr[0], (length/2));
        merge_sort(&arr[length/2], (length - length/2));
        merge_parts(arr, length);
    }
}

int main()
{
    int length;
    scanf("%d", &length);
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
    }

    int *arr;
    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    SORTING_ALGO_CALL(arr, length);

    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }

    free(arr);
    return 0;
}

EDIT:

The book I am reading "Introduction to ALgorithms 3rd Edition" by Cormen mentions a sentinal value be placed at the end of two subarrays. That, if implemented, can result in better efficiency but I am not sure what to use as a sentinal value.

Edited code after Josay's comments

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

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This while and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(i = 0; i < j; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,         mid);
        merge_sort(arr + mid,   length - mid);
        merge_parts(arr, length);
    }
}

int main()
{
    int length;
    scanf("%d", &length);
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
    }

    int *arr = malloc(sizeof(int) * length);
    if (arr == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    merge_sort(arr, length);

    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }

    free(arr);
    return 0;
}
share|improve this question
    
@Josay Any comments regarding updated code? –  Aseem Bansal Jul 8 '13 at 18:25
    
I still think that the way you ask for the length is not really user-friendly but everything else looks good to me. –  Josay Jul 8 '13 at 21:43
add comment

1 Answer

up vote 3 down vote accepted

I've slightly reorganised your code to make it easier to follow.

void merge_parts(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    int ans[length];
    //This for and next if-else puts the merged array into temporary array ans
    //in a sorted manner
    int mid = length/2;
    int i = 0, k = 0, j = mid;
    while (i < mid && j < length){
        ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    // Only one of the two loops will apply
    while(j < length){
        ans[k++] = arr[j++];
    }
    while(i < mid){
        ans[k++] = arr[i++];
    }

    //This for-loop puts array ans into original array arr
    for(int i = 0; i < length; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        int mid = length/2;
        merge_sort(arr,     mid);
        merge_sort(arr+mid, length - mid);
        merge_parts(arr, length);
    }
}

int main()
{
    int length;
    for (;;)
    {
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
        printf("\nYou entered length = %d\n", length);
        if (length>=1) break;
    }

    int *arr = malloc(sizeof(int) * length);
    if (!arr)
    {
        perror("The following error occurred");
        exit(-1);
    }

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

    merge_sort(arr, length);

    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }

    free(arr);
    return 0;
}

Then for the only optimisation I can think of, you could avoid some copying : when j < length after the main loop, it corresponds to a situation where the end of arr is already sorted in the right place. Thus, you don't need to copy it from arr to ans and then from ans to arr.

int mid = length/2;
int i = 0, k = 0, j = mid;
while (i < mid && j < length){
    ans[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
}

while(i < mid){
    ans[k++] = arr[i++];
}

//This for-loop puts array ans into original array arr
for(i = 0; i < j; i++){
    arr[i] = ans[i];
}
share|improve this answer
    
Thanks, I posted my edited code. –  Aseem Bansal Jul 8 '13 at 14:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.