Python Program for Merge Sort

What is merge sort ?

Merge Sort Algorithm

• Divide the unsorted list into multiple sub lists using mid index ( ( start index + end index) /2) until each sub list contains single element.
• Take two adjacent pairs of sub list and merge them as list of 2 elements.
• Repeat step 2 process till merging single sorted list of all elements.

Merge Sorting Steps

Merge Sorting Time complexity

Merge Sort Python Program

#!/usr/bin/python                                                               
                                                                                
def merge_list(list_vals,  start_index, mid_index, end_index):                  
    # Starting position of both parts                                           
    p = start_index;                                                            
    q = mid_index + 1;                                                          
                                                                                
    sorted_list_vals= [];                                                       
                                                                                
    for i in range(start_index, end_index+1):                                   
        # Checks whether 1st part is end or not.                                
        if (p > mid_index):                                                     
            sorted_list_vals.append(list_vals[q]);                              
            q += 1;                                                             
                                                                                
        # Checks whether 2nd part is end or not.                                
        elif (q > end_index):                                                   
            sorted_list_vals.append(list_vals[p]);                              
            p += 1;                                                             
                                                                                
        # Checks which part has samller element.                                
        elif (list_vals[p] < list_vals[q]):                                     
            sorted_list_vals.append(list_vals[p]);                              
            p += 1;                                                             
                                                                                
        else:                                                                   
            sorted_list_vals.append(list_vals[q]);                              
            q += 1;                                                             
                                                                                
    for p in range(0, len(sorted_list_vals)):                                   
        list_vals[start_index] = sorted_list_vals[p];                           
        start_index += 1;                                                       
                                                                                
                                                                                
def merge_sort(list_vals, start_index, end_index):                              
    if (start_index < end_index):                                               
        # finding mid index                                                     
        mid_index = (start_index + end_index ) / 2;                             
        # sorting 1st part of the array.                                        
        merge_sort(list_vals, start_index, mid_index);                          
        # sorting 2nd part of the array.                                        
        merge_sort(list_vals, mid_index+1, end_index);                          
        # merge the both parts, comparing elements                              
        merge_list(list_vals, start_index, mid_index, end_index);               
                                                                                
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    merge_sort(list_vals, 0, len(list_vals)-1);                                 
    print("Sorted list elements: %s" % str(list_vals));                                                                                                                                             

$ python  merge_sort.py 
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]