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.

Tags

Merge sort Algorithm, pseudocode Python

Similar Programs Chapter Last Updated
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