Merge sort explained - python coding

Merge sort explained - python coding


Published at - Sep 14, 2021

In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Some important points

  • Based on Divide and conquer strategy
  • Requires extra space to hold the two halves

Time & Space Complexity

Worst complexityn*log(n)
Average complexityn*log(n)
Best complexityn*log(n)
Space complexityn

Algorithm

MergeSort(arr[], l, r)

If r > l

Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
Call mergeSort for first half: Call mergeSort(arr, l, m)
Call mergeSort for second half: Call mergeSort(arr, m+1, r)
Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)

Python program for implementation of MergeSort 

def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 # Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
            k+= 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1
  
# Code to print the list 
def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end =" ") 
    print() 
  
# driver code to test the above code 
if __name__ == '__main__': 
    arr = [12, 11, 13, 5, 6, 7]  
    print ("Given array is", end ="\n")  
    printList(arr) 
    mergeSort(arr) 
    print("Sorted array is: ", end ="\n") 
    printList(arr)

 All programs will print sorted array as output.

I hope you like this article, to learn more about articles like this you can click here. Thank you for reading.

Thank You!

 

 



About author

Harendra
Harendra Kanojiya

Hi I'm Harendra Kumar Kanojiya. Currently I am FSD (Full-stack developer) and I have expertise with Angular ,PHP, Node JS, Laravel, Codeigniter and front end. Done few live projects and portfolio work in above.



Related Posts -

Follow Us

Follow us on facebook Click Here

Facebook QR
Scan from mobile
Join our telegram channel Click Here
Telegram QR
Scan from mobile