/*Learning recursion via merge sort. Why does it crash when I try sorting more than 12 numbers?*/

​

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#define MAGIC_NUMBER 256

​

int *malloc_calls[MAGIC_NUMBER]; //store result of each malloc() here

int malloc_count = 0; //keep track of malloc calls

​

int* sort (int *random, int length);

int* merge (int *right_half_sorted, int right_half_length, int *left_half_sorted, int left_half_length);

​

int main(int argc, char const *argv[])

{

printf("Enter unsorted numbers: ");

char string[MAGIC_NUMBER];

fgets(string, MAGIC_NUMBER, stdin);

int length = strlen(string) - 1;

​

int random_array[length];

​

for (size_t i = 0; i < length; i++)

{

random_array[i] = string[i] - 48; //covert string number to regular number

}

int *sorted_array = sort(random_array, length);

for (int i = 0; i < length; i++)

{

printf("%i ", sorted_array[i]); //print sorted numbers separated by space

}

for (size_t i = 0; i < malloc_count; i++)

{

free(malloc_calls[i]); //free all mallocs

}

return 0;

}

​

int* sort (int *random, int length)

{

if(length < 1){

printf("Invalid Length");

}

else if (length == 1)

{

return random;

}

else

{

int r = length%2; //store remainder in case length is odd

int l1 = length / 2;

int l2 = l1 + r; //remainder added so nothing is lost during division

​

int *right_half = random;

int *left_half = random + l1;

​

int *sorted1 = sort(right_half, l1);

int *sorted2 = sort(left_half, l2);

​

int *merged = merge(sorted1, l1, sorted2, l2);

}

}

​

int* merge (int *right_half_sorted, int right_half_length, int *left_half_sorted, int left_half_length)

{

int combined_length = right_half_length + left_half_length;

int* new_sorted_array = malloc(combined_length);

​

int i = 0; //left half index

int j = 0; //right half index

int k = 0; //new array index

​

for (size_t k = 0; k < combined_length; k++)

{

if (i == left_half_length) //reached the end of left half

{

new_sorted_array[k] = right_half_sorted[j];

j++;

}

else if (j == right_half_length) //reached the end of right half

{

new_sorted_array[k] = left_half_sorted[i];

i++;

}

else

{

if (left_half_sorted[i] < right_half_sorted[j]) {

new_sorted_array[k] = left_half_sorted[i];

        i++;

}

else {

new_sorted_array[k] = right_half_sorted[j];

j++;

}

}

}

​

malloc_calls[malloc_count] = new_sorted_array; //store result of malloc call to free later

malloc_count++;

return new_sorted_array;

​

    }