Merge Sort In Python

Chapter: Python Last Updated: 01-12-2020 13:20:57 UTC

Program:

            /* ............... START ............... */
                
def merge_sort(arr):
    if len(arr) <= 1:
        return

    mid = len(arr)//2

    left = arr[:mid]
    right = arr[mid:]

    merge_sort(left)
    merge_sort(right)

    merge_two_sorted_lists(left, right, arr)

def merge_two_sorted_lists(a,b,arr):
    len_a = len(a)
    len_b = len(b)

    i = j = k = 0

    while i < len_a and j < len_b:
        if a[i] <= b[j]:
            arr[k] = a[i]
            i+=1
        else:
            arr[k] = b[j]
            j+=1
        k+=1

    while i < len_a:
        arr[k] = a[i]
        i+=1
        k+=1

    while j < len_b:
        arr[k] = b[j]
        j+=1
        k+=1

if __name__ == '__main__':
    test_cases = [
        [10, 3, 15, 7, 8, 23, 98, 29],
        [],
        [3],
        [9,8,7,2],
        [1,2,3,4,5]
    ]

    for arr in test_cases:
        merge_sort(arr)
        print(arr)

                /* ............... END ............... */
        

Output

[3, 7, 8, 10, 15, 23, 29, 98]
[]
[3]
[2, 7, 8, 9]
[1, 2, 3, 4, 5]

Notes:

  • As like quick sort mergesort is uses divide and conquer rule. In merge sort we will divide the array and sort to make to one array.
  • Please find the below steps in merge sort.
  • Find the middle point of array by dividing into half.
  • Call merge_sort (first half) to sort first half.
  • Call merge_sort (first half) to sort Second half.
  • merge_two_sorted_lists (firthalf,secondhalf,arr) function will sort the first half and second half to make to one aray.
Similar Programs Chapter Last Updated
Python Tuples Example Python 19-11-2021
Python Iterator Example Python 12-11-2021
Python Lambda Functions Python 11-11-2021
Integer To String In Python Python 22-10-2021
Python Datetime Format Python 21-10-2021
Range Function In Python | Python range () Python 11-10-2021
Python Desktop Notification Popup In Linux Python 10-07-2021
Python JSON Parser Example | How To Parse JSON In Python Python 25-06-2021
Python PIP | How To Install Packages In Python Python 16-06-2021
How To Access Python Dictionary Python 14-06-2021
Dictionary In Python Examples Python 10-06-2021
Shortest Path Algorithm In Python Python 23-02-2021
Kruskal Algorithm In Python Python 28-11-2020
Python Mysql Connector Example Python 21-11-2020
Add To Set Python Python 05-10-2018
Set In Python Python 05-10-2018
List In Python Python 29-09-2018
Integer To String Python Python 29-09-2018
Python Variables Python 21-09-2018
Python String Contains Python 15-09-2018
String In Python Python 22-09-2018
Python Switch Statement Python 20-09-2018
Python Function Example Python 14-09-2018
Python If Statement Python 14-09-2018
Area Of Triangle In Python Python 14-09-2018
Python Square Root Python 22-09-2018
Add Two Numbers In Python Python 13-09-2018
Python Comments Python 22-09-2018
Python Hello World Python 14-09-2018

1