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