Divide and conquer paradigm and recursion in C - Merge sort example

Question

I can't understand how divide and conquer algorithms are implemented in C. By that I mean that I understand the algorithm but don't understand why and how it works when written in C.

What are the instructions executed and what determines the order of their execution in the following example?

In other words, why do "merge_sort initialization", "merge_sort first", "merge_sort second" and "merging" appear the way they do?

#include<stdio.h>

int arr[8]={1, 2, 3, 4, 5, 6, 7, 8};

int main()
{
    int i;
    merge_sort(arr, 0, 7);

    printf("Sorted array:");

    for(i = 0; i < 8; i++)
        printf("%d", arr[i]);

    return 0;
}

int merge_sort(int arr[],int low,int high)
{
    printf("\nmerge_sort initialization\n");

    int mid;

    if(low < high) 
    {
        mid = (low + high) / 2;

        // Divide and Conquer
        merge_sort(arr, low, mid); 
        printf("\n merge_sort first\n");

        merge_sort(arr, mid + 1, high); 
        printf("\n merge_sort second\n");

        // Combine
        merge(arr, low, mid, high); 
        printf("\nmerging\n");
    }

    return 0;
}

int merge(int arr[], int l, int m, int h)
{
    int arr1[10], arr2[10];
    int n1, n2, i, j, k;
    n1 = m - l + 1;
    n2 = h - m;

    for(i = 0; i < n1; i++)
        arr1[i] = arr[l + i];

    for(j = 0; j < n2; j++)
        arr2[j] = arr[m + j + 1];

    arr1[i] = 9999;
    arr2[j] = 9999;

    i = 0;
    j = 0;

    for(k = l; k <= h; k++)
    {
        if(arr1[i] <= arr2[j])
            arr[k] = arr1[i++];
        else
            arr[k] = arr2[j++];
    }

    return 0;
}

Thanks in advance for your answers.

Answer 1

I am not sure why you are asking people to make you understand the algorithm. I can just assist you you but you have to go through it.

In merge short you have to cut the array in two pieces. suppose you have 10 elements then high=0 and low=10-1=1. mid = (9+0)/2 = 4. So, you have divided the main array to 2 parts from 1th element to 5th and from 6th element to 10th (1..10). When ever you have more than one element in a piece you cut it into two again. At the end merge them i.e. add arrays again but in ascending order. Finally you get a single array sorted. Its very tough to explain every piece. I think this link from wiki can help. http://en.wikipedia.org/wiki/Merge_sort

Now comes the function calling. main function is calling merge_sort it will pass low and hight (the full range of array) but within this function the merge_sort will be called by himself twice with first half range (starting to mid way and after midway to last element). Each call will again do the same (divide the array and call with first half and send half). This process will go on. merge function will add the array in sorted manner. Thats all you need. If you are not clear print or debug the value of parameters.