Python Program for Merge Sort

What is merge sort ?

Merge sort is a divide-and-conquer algorithm, here breaking down a list into multiple sub lists till each sub list consists of a single element and then merging all sub lists in order to get a sorted list.

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

Merge Sorting Time complexity

Number of elements in the list is N, N is divided into a max of log N sub lists, and merging all sub lists into a single list takes O(N) time, Worst case run time O(N Log N).

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));                                                                                                                                             
Output:
$ 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]


Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^