programs-in-python/Merge_Sort.py at main · Apurvgeek/programs-in-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#Runtine is O(nlogn)
def merge(arr, l, m, r):
    temp_arr = []
    i = l
    j = m
    while i < m and j < r:
        if arr[i] > arr[j]:
            temp_arr.append(arr[j])
            j += 1
        elif arr[i] < arr[j]:
            temp_arr.append(arr[i])
            i += 1
        else:
            temp_arr.append(arr[i])
            i += 1
            temp_arr.append(arr[j])
            j += 1
    temp_arr.extend(arr[i:m])
    temp_arr.extend(arr[j:r])
    for i in range(len(temp_arr)):
        arr[l+i] = temp_arr[i]

def Merge_Sort(arr, l, r):
    #code here
    length = r - l + 1
    if length == 2:
        if arr[l] > arr[r]:
            arr[l], arr[r] = arr[r], arr[l]
    elif length > 2:
        Merge_Sort(arr, l, length//2 + l)
        Merge_Sort(arr, length//2 + l + 1, r)
        merge(arr, l, length//2 + l + 1, r+1)

array = list(map(int, input().split()))

Merge_Sort(array)
print(array)