merge sort in python

1def merge_sort(arr):
2    # The last array split
3    if len(arr) <= 1:
4        return arr
5    mid = len(arr) // 2
6    # Perform merge_sort recursively on both halves
7    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
8
9    # Merge each side together
10    return merge(left, right, arr.copy())
11
12
13def merge(left, right, merged):
14
15    left_cursor, right_cursor = 0, 0
16    while left_cursor < len(left) and right_cursor < len(right):
17      
18        # Sort each one and place into the result
19        if left[left_cursor] <= right[right_cursor]:
20            merged[left_cursor+right_cursor]=left[left_cursor]
21            left_cursor += 1
22        else:
23            merged[left_cursor + right_cursor] = right[right_cursor]
24            right_cursor += 1
25            
26    for left_cursor in range(left_cursor, len(left)):
27        merged[left_cursor + right_cursor] = left[left_cursor]
28        
29    for right_cursor in range(right_cursor, len(right)):
30        merged[left_cursor + right_cursor] = right[right_cursor]
31
32    return merged

1def mergeSort(myList):
2    if len(myList) > 1:
3        mid = len(myList) // 2
4        left = myList[:mid]
5        right = myList[mid:]
6
7        # Recursive call on each half
8        mergeSort(left)
9        mergeSort(right)
10
11        # Two iterators for traversing the two halves
12        i = 0
13        j = 0
14        
15        # Iterator for the main list
16        k = 0
17        
18        while i < len(left) and j < len(right):
19            if left[i] < right[j]:
20              # The value from the left half has been used
21              myList[k] = left[i]
22              # Move the iterator forward
23              i += 1
24            else:
25                myList[k] = right[j]
26                j += 1
27            # Move to the next slot
28            k += 1
29
30        # For all the remaining values
31        while i < len(left):
32            myList[k] = left[i]
33            i += 1
34            k += 1
35
36        while j < len(right):
37            myList[k]=right[j]
38            j += 1
39            k += 1
40
41myList = [54,26,93,17,77,31,44,55,20]
42mergeSort(myList)
43print(myList)

1def mergesort(list1):
2    if len(list1) >1 :
3    
4        mid = len(list1)//2
5        left_list = list1[:mid]
6        right_list = list1[mid:]
7        mergesort(left_list) #Using recursion down here for the sub list
8        mergesort(right_list) #Using recursion down here for the sub list
9        i = 0
10        j = 0
11        k = 0
12        while i<len(left_list) and j<len(right_list):
13            if left_list[i]< right_list[j]:
14                list1[k] = left_list[i]
15                i+=1
16                k+=1
17            else:
18                list1[k] = right_list[j]
19                j+=1
20                k+=1
21        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)  
22            list1[k] = left_list[i]
23            i+=1
24            k+=1
25
26        while j < len(right_list):
27            list1[k] = right_list[j]
28            j+=1
29            k+=1
30#Start watching from here and then as when function call will come then go check function
31n = int(input("Enter how many element you want in the list : "))
32list1 = [int(input()) for i in range(n)]
33mergesort(list1)
34print("sorted list : " + str(list1))

1def mergeSort(arr):
2
3    if len(arr) > 1:
4
5        a = len(arr)//2
6
7        l = arr[:a]
8
9        r = arr[a:]
10
11        # Sort the two halves
12
13        mergeSort(l)
14
15        mergeSort(r) 
16
17        b = c = d = 0
18
19        while b < len(l) and c < len(r):
20
21            if l[b] < r[c]:
22
23                arr[d] = l[b]
24
25                b += 1
26
27            else:
28
29                arr[d] = r[c]
30
31                c += 1
32
33            d += 1
34
35        while b < len(l):
36
37            arr[d] = l[b]
38
39            b += 1
40
41            d += 1
42
43        while c < len(r):
44
45            arr[d] = r[c]
46
47            c += 1
48
49            d += 1
50
51
52def printList(arr):
53
54    for i in range(len(arr)):
55
56        print(arr[i], end=" ")
57
58    print()
59 
60
61# Driver program
62
63if __name__ == '__main__':
64
65    arr = [0,1,3,5,7,9,2,4,6,8] 
66
67    mergeSort(arr) 
68
69    print("Sorted array is: ")
70
71    printList(arr)
72
73 
74

1def mergeSort(arr): 
2    if len(arr) >1: 
3        mid = len(arr)//2 # Finding the mid of the array 
4        L = arr[:mid] # Dividing the array elements  
5        R = arr[mid:] # into 2 halves 
6  
7        mergeSort(L) # Sorting the first half 
8        mergeSort(R) # Sorting the second half 
9  
10        i = j = k = 0
11          
12        # Copy data to temp arrays L[] and R[] 
13        while i < len(L) and j < len(R): 
14            if L[i] < R[j]: 
15                arr[k] = L[i] 
16                i+= 1
17            else: 
18                arr[k] = R[j] 
19                j+= 1
20            k+= 1
21          
22        # Checking if any element was left 
23        while i < len(L): 
24            arr[k] = L[i] 
25            i+= 1
26            k+= 1
27          
28        while j < len(R): 
29            arr[k] = R[j] 
30            j+= 1
31            k+= 1
32  
33# Code to print the list 
34def printList(arr): 
35    for i in range(len(arr)):         
36        print(arr[i], end =" ") 
37    print() 
38  
39# driver code to test the above code 
40if __name__ == '__main__': 
41    arr = [12, 11, 13, 5, 6, 7]  
42    print ("Given array is", end ="\n")  
43    printList(arr) 
44    mergeSort(arr) 
45    print("Sorted array is: ", end ="\n") 
46    printList(arr)