❮ Python String Ljust Python String Len ❯

Python Merge Sort

Merge sort (English: Merge sort, or mergesort) is an efficient sorting algorithm that is based on the merge operation. This algorithm is a very typical application of the Divide and Conquer strategy.

Divide and Conquer:

Divide: Recursively divide the current sequence into two halves.
Integrate: Merge the sub-sequences obtained from the previous step while maintaining their order.

Example

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r - m 

    # Create temporary arrays
    L = [0] * (n1)
    R = [0] * (n2)

    # Copy data to temporary 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 temporary 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 any
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1

    # Copy the remaining elements of R[], if any
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1

def mergeSort(arr,l,r): 
    if l < r: 

        m = int((l+(r-1))/2)

        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 

arr = [12, 11, 13, 5, 6, 7] 
n = len(arr) 
print ("Given array") 
for i in range(n): 
    print ("%d" %arr[i]), 

mergeSort(arr,0,n-1) 
print ("\n\nSorted array") 
for i in range(n): 
    print ("%d" %arr[i]),

Executing the above code produces the following output:

Given array
12
11
13
5
6
7

Sorted array
5
6
7
11
12
13

Python3 Examples

❮ Python String Ljust Python String Len ❯