Merge Sort Using Recursion in C
Merge sort is one of the best algorithms used for sorting after quick sort. It is a divide and conquer algorithm in which the given set of numbers is divided into two halves until it reaches the base level and then it is sorted up. Take a look at the picture below for better understanding.
So in the below program the merge_divide function will be used to divide the array into sub parts as you see in the animation above. The merge_sort function is used to sort the elements in an ascending order.
WORK FLOW :
- merge_divide takes 3 arguments. The array, starting position of the array and the ending position. We check if the starting position is lesser than ending position and if so we find the middle element and store in the variable r.
- We recursively call the function passing the value of p and r (denoting the first half) and call it again passing r+1 and q (denoting the second half). It will again call the function so on until the values of p and q are equal or p < q.
- At the final recursive call it calls the merge_sort (taking the array, starting position, ending position as arguments) function which sorts the elements of the array within the given index values.
Got any doubt with the above program ? Feel free to comment and get your doubts cleared :)