Answers for "mergesort python"

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

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)

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))

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]);

Merge Sort Python

def mergeSort(arr):

    if len(arr) > 1:

        a = len(arr)//2

        l = arr[:a]

        r = arr[a:]

        # Sort the two halves

        mergeSort(l)

        mergeSort(r) 

        b = c = d = 0

        while b < len(l) and c < len(r):

            if l[b] < r[c]:

                arr[d] = l[b]

                b += 1

            else:

                arr[d] = r[c]

                c += 1

            d += 1

        while b < len(l):

            arr[d] = l[b]

            b += 1

            d += 1

        while c < len(r):

            arr[d] = r[c]

            c += 1

            d += 1


def printList(arr):

    for i in range(len(arr)):

        print(arr[i], end=" ")

    print()
 

# Driver program

if __name__ == '__main__':

    arr = [0,1,3,5,7,9,2,4,6,8] 

    mergeSort(arr) 

    print("Sorted array is: ")

    printList(arr)