Recursive implementation of merge sort

Question

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?

#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; } 

The book I am reading is Introduction to Algorithms 3rd Edition by Cormen. It mentions a sentinel value be placed at the end of two subarrays. That, if implemented, it can result in better efficiency. But I am not sure what to use as a sentinel value.

Answer 1

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]; }