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  :

  1. 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.
  2. 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. 
  3. 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 :)

Comments

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. This comment has been removed by a blog administrator.

    ReplyDelete

Post a Comment

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming