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.