-
Notifications
You must be signed in to change notification settings - Fork 1
/
mergeSort.py
61 lines (60 loc) · 1.67 KB
/
mergeSort.py
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#Python program for implementation of MergeSort
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m# create temp arrays
#L = [0 for range
#R = [0] * (n2)
L=[0 for i in range (int(n1))]
R=[0 for j in range(int(n2))]
# Copy data to temp arrays L[] and R[]
for i in range(0 , int(n1)):
L[i] = arr[l + i]
for j in range(0 , int(n2)):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i = 0 # Initial indexof first subarray
j = 0 # Initial index of second subarray
k = l # Initial index of merged subarray
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
if l < r:
# Same as (l+r)/2, but avoids overflow for
# large l and h
m = (l+(r-1))/2# Sort first and second halves
mergeSort(arr, int(l), int(m))
mergeSort(arr, int(m+1), int(r))
merge(arr, int(l), int(m), int(r))
num=list()
m=input("enter number of elements:")
print("Enter elements")
for i in range(0,int(m)):
k=input("num: ")
num.append(int(k))
print(" Array :",num)
n=len(num)
mergeSort(num,0,int(n-1))
print(" Array :",num)