PYTHON

how to do merge sort in python

ev = [12,42,53,14,86,34]

def Division(ev):
    i = 0
    j = 0
    k = 0
    if len(ev) > 1:
        middle = (0 + (len(ev)//2))
        l = ev[0:middle]
        r = ev[middle:]
        Division(l)
        Division(r)

        while (i < len(l) and j < len(r)):
            if l[i] <= r[j]:
                ev[k] = l[i]
                i = i + 1
                k = k + 1
            else:
                ev[k] = r[j]
                j = j + 1
                k = k + 1
                
        while i < len(l):
               ev[k] = l[i]
               i = i + 1
               k = k + 1

        while j < len(r):
               ev[k] = r[j]
               j = j + 1
               k = k + 1

def printList(ev):
    for x in range(len(ev)):
        print(ev[x],end=" ")
    print()

# Driver Code
print("Before:",end=" ")
printList(ev)
Division(ev)
print()
print("After:",end=" ")
printList(ev)

merge sort python

"""Mergesort
	The cleaner version than geeks4geeks. Although check that code out too!
"""
## Method 1: Two functions
def mergesort(lst):
    # Is sortable
    if len(lst) > 1:
        # Get mid-point
        mid = len(lst) // 2
        
        # Recursive Partition
        left = mergesort(lst[:mid])
        right = mergesort(lst[mid:])
        
        # Merging
        return merge(left, right)
    return lst

def merge(left, right):
    new = []
    
    # Left and right not empty
    while left and right:
        # Compare 1st elements of left and right, sort accordingly
        if left[0] < right[0]:
            new.append(left.pop(0))
        else:
            new.append(right.pop(0))
    
    # Append the leftover nums
    return new + left + right

## Method 2: Nested functions
def merge(nums):
    # Recursive partition
    if len(nums) > 1:
        # Midpoint
        mid = len(nums) // 2
        
        left = merge(nums[:mid])
        right = merge(nums[mid:])
        
        # Sorting
        def go(left, right):
            newlist = []
            
            # Sort by comparing 1st elements of both lists
            while left and right:
                if left[0] < right[0]:
                    newlist.append(left.pop(0))
                else:
                    newlist.append(right.pop(0))
                    
            # Cleanup unsorted elements            
            return newlist + left + right
        return go(left, right)
    return nums

Python merge sort algorithm

def mergeSort(A):
    if len(A) > 1:
        print('Splitting' , A)
        mid = len(A)//2
        left = A[:mid]
        right = A[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                A[k] = left[i]
                i = i+1
            else:
                A[k] = left[i]
                j = j+1
            k = k+1
        while i < len(left):
            A[k] = left[i]
            i = i+1
            k = k+1
        while j < len(right):
            A[k] = right[j]
            j = j+1
            k = k+1
        print('merging' , A)
        return(A)

Merge sorting in python

# Merge Sorting:

def merge(a,b):
    merged_list = []
    len_a,len_b = len(a),len(b)
    index_a,index_b = 0,0

    while index_a < len_a and index_b < len_b:
        if a[index_a] < b[index_b]:
            merged_list.append(a[index_a])
            index_a += 1
        else:
            merged_list.append(b[index_b])
            index_b += 1

    if index_a < len_a:
        merged_list.extend(a[index_a:])
    elif index_b < len_b:
        merged_list.extend(b[index_b:])
    return merged_list

# Now merge sorting:
def merge_sort(L):
    if len(L) <= 1:
        return L
    mid = len(L)//2
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    return merge(left,right)

# input list:
L = [[4,7,2,3],[10],[10,9,8,7,6],[2,3,1],[1,2],[2,1]]
total_sorted_list = []
for i in L:
    sorted_list = merge_sort(i)
    print("Original List:",i)
    print("Sorted List:",sorted_list)
    print()

# Output:
Original List: [4, 7, 2, 3]
Sorted List: [2, 3, 4, 7]

Original List: [10]
Sorted List: [10]

Original List: [10, 9, 8, 7, 6]
Sorted List: [6, 7, 8, 9, 10]

Original List: [2, 3, 1]
Sorted List: [1, 2, 3]

Original List: [1, 2]
Sorted List: [1, 2]

Original List: [2, 1]
Sorted List: [1, 2]

merge sort code in python

# Python program for implementation of MergeSort
 
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
 
 
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
 
 
# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
    print("%d" % arr[i],end=" ")
 
mergeSort(arr, 0, n-1)
print("

Sorted array is")
for i in range(n):
    print("%d" % arr[i],end=" ")
 
# This code is contributed by Mohit Kumra

python merge sort

# Python program for implementation of MergeSort
 
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
 
 
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
 
 
# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
    print("%d" % arr[i],end=" ")
 
mergeSort(arr, 0, n-1)
print("

Sorted array is")
for i in range(n):
    print("%d" % arr[i],end=" ")