merge sort in python
Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems.

These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem
but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem.


The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively,
it operates as follows.


here is a basic code in python


from __future__ import division
import sys
SENTINEL = sys.maxint

def merge(input_array,first,middle,last):
    n1 = middle - first + 1
    n2 = last - middle

    L = [None for t in range(n1+1)]
    R = [None for t in range(n2+1)]

    
    for i in range(n1):
        L[i] = input_array[first + i - 1]
        
    for j in range(n2):
        R[j] =input_array[middle + j]
         

    L[n1] = SENTINEL
     
    R[n2] = SENTINEL
     

    i = 0
    j = 0 
    for k in range(first-1,last): 
        if L[i] <= R[j]:
            input_array[k] = L[i]
            i = i + 1
        else:
            input_array[k] = R[j]
            j = j + 1



def mergeSort(input_array,first,last):
    if first < last:
        middle =  int((first + last)/2) 
        mergeSort(input_array,first,middle)
        mergeSort(input_array,middle + 1,last)
        
        merge(input_array,first,middle,last)


arr = [5,2,4,7,1,3,2,6]
 
mergeSort(arr,1,len(arr))
print arr

Hope this helps ;)

Varun Pant

merge sort in python  by  Varun Pant