merge sort python code example

Example 1: Merge Sort python

def merge_sort(arr):
    # The last array split
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    # Perform merge_sort recursively on both halves
    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])

    # Merge each side together
    return merge(left, right, arr.copy())


def merge(left, right, merged):

    left_cursor, right_cursor = 0, 0
    while left_cursor < len(left) and right_cursor < len(right):
      
        # Sort each one and place into the result
        if left[left_cursor] <= right[right_cursor]:
            merged[left_cursor+right_cursor]=left[left_cursor]
            left_cursor += 1
        else:
            merged[left_cursor + right_cursor] = right[right_cursor]
            right_cursor += 1
            
    for left_cursor in range(left_cursor, len(left)):
        merged[left_cursor + right_cursor] = left[left_cursor]
        
    for right_cursor in range(right_cursor, len(right)):
        merged[left_cursor + right_cursor] = right[right_cursor]

    return merged

Example 2: merge sort in python

def mergeSort(myList):
    if len(myList) > 1:
        mid = len(myList) // 2
        left = myList[:mid]
        right = myList[mid:]

        # Recursive call on each half
        mergeSort(left)
        mergeSort(right)

        # Two iterators for traversing the two halves
        i = 0
        j = 0
        
        # Iterator for the main list
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
              # The value from the left half has been used
              myList[k] = left[i]
              # Move the iterator forward
              i += 1
            else:
                myList[k] = right[j]
                j += 1
            # Move to the next slot
            k += 1

        # For all the remaining values
        while i < len(left):
            myList[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            myList[k]=right[j]
            j += 1
            k += 1

myList = [54,26,93,17,77,31,44,55,20]
mergeSort(myList)
print(myList)

Example 3: merge sort in python

def mergesort(list1):
    if len(list1) >1 :
    
        mid = len(list1)//2
        left_list = list1[:mid]
        right_list = list1[mid:]
        mergesort(left_list) #Using recursion down here for the sub list
        mergesort(right_list) #Using recursion down here for the sub list
        i = 0
        j = 0
        k = 0
        while i<len(left_list) and j<len(right_list):
            if left_list[i]< right_list[j]:
                list1[k] = left_list[i]
                i+=1
                k+=1
            else:
                list1[k] = right_list[j]
                j+=1
                k+=1
        while i < len(left_list): # I did this as for the end condition of above loop as when i or j will be equal to len(left/right list)  
            list1[k] = left_list[i]
            i+=1
            k+=1

        while j < len(right_list):
            list1[k] = right_list[j]
            j+=1
            k+=1
#Start watching from here and then as when function call will come then go check function
n = int(input("Enter how many element you want in the list : "))
list1 = [int(input()) for i in range(n)]
mergesort(list1)
print("sorted list : " + str(list1))

Example 4: merge sort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function merge(list, start, midpoint, end) {
    const left = list.slice(start, midpoint);
    const right = list.slice(midpoint, end);
    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
        if (topLeft >= left.length) {
            list[i] = right[topRight++];
        } else if (topRight >= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] < right[topRight]) {
            list[i] = left[topLeft++];
        } else {
            list[i] = right[topRight++];
        }
    }
}

function mergesort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length;
    }
    if (end - start > 1) {
        const midpoint = ((end + start) / 2) >> 0;
        mergesort(list, start, midpoint);
        mergesort(list, midpoint, end);
        merge(list, start, midpoint, end);
    }
    return list;
}

mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

Example 5: merge sort algo

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)