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

1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
3
4function merge(list, start, midpoint, end) {
5    const left = list.slice(start, midpoint);
6    const right = list.slice(midpoint, end);
7    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
8        if (topLeft >= left.length) {
9            list[i] = right[topRight++];
10        } else if (topRight >= right.length) {
11            list[i] = left[topLeft++];
12        } else if (left[topLeft] < right[topRight]) {
13            list[i] = left[topLeft++];
14        } else {
15            list[i] = right[topRight++];
16        }
17    }
18}
19
20function mergesort(list, start = 0, end = undefined) {
21    if (end === undefined) {
22        end = list.length;
23    }
24    if (end - start > 1) {
25        const midpoint = ((end + start) / 2) >> 0;
26        mergesort(list, start, midpoint);
27        mergesort(list, midpoint, end);
28        merge(list, start, midpoint, end);
29    }
30    return list;
31}
32
33mergesort([4, 7, 2, 6, 4, 1, 8, 3]);

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