Skip to content

Commit f25aca9

Browse files
author
codehouseindia
authored
Merge pull request codehouseindia#467 from GustavoVMO/master
Merge Sort in Python
2 parents d73114a + 8cfd6bb commit f25aca9

3 files changed

Lines changed: 234 additions & 0 deletions

File tree

‎merge.py‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#https://www.facebook.com/permalink.php?story_fbid=2830418890577388&id=100008279138695
2+
#Subscribed by Code House
3+
4+
5+
# Python program for implementation of MergeSort
6+
7+
# Merges two subarrays of arr[].
8+
# First subarray is arr[l..m]
9+
# Second subarray is arr[m+1..r]
10+
def merge(arr, l, m, r):
11+
n1 = m - l + 1
12+
n2 = r- m
13+
14+
# create temp arrays
15+
L = [0] * (n1)
16+
R = [0] * (n2)
17+
18+
# Copy data to temp arrays L[] and R[]
19+
for i in range(0 , n1):
20+
L[i] = arr[l + i]
21+
22+
for j in range(0 , n2):
23+
R[j] = arr[m + 1 + j]
24+
25+
# Merge the temp arrays back into arr[l..r]
26+
i = 0 # Initial index of first subarray
27+
j = 0 # Initial index of second subarray
28+
k = l # Initial index of merged subarray
29+
30+
while i < n1 and j < n2 :
31+
if L[i] <= R[j]:
32+
arr[k] = L[i]
33+
i += 1
34+
else:
35+
arr[k] = R[j]
36+
j += 1
37+
k += 1
38+
39+
# Copy the remaining elements of L[], if there
40+
# are any
41+
while i < n1:
42+
arr[k] = L[i]
43+
i += 1
44+
k += 1
45+
46+
# Copy the remaining elements of R[], if there
47+
# are any
48+
while j < n2:
49+
arr[k] = R[j]
50+
j += 1
51+
k += 1
52+
53+
# l is for left index and r is right index of the
54+
# sub-array of arr to be sorted
55+
def mergeSort(arr,l,r):
56+
if l < r:
57+
58+
# Same as (l+r)//2, but avoids overflow for
59+
# large l and h
60+
m = (l+(r-1))//2
61+
62+
# Sort first and second halves
63+
mergeSort(arr, l, m)
64+
mergeSort(arr, m+1, r)
65+
merge(arr, l, m, r)
66+
67+
68+
# Driver code to test above
69+
arr = [12, 11, 13, 5, 6, 7]
70+
n = len(arr)
71+
print ("Given array is")
72+
for i in range(n):
73+
print ("%d" %arr[i]),
74+
75+
mergeSort(arr,0,n-1)
76+
print ("\n\nSorted array is")
77+
for i in range(n):
78+
print ("%d" %arr[i]),

‎mergepython.py‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#https://www.facebook.com/permalink.php?story_fbid=2830418890577388&id=100008279138695
2+
#Subscribed by Code House
3+
4+
5+
# Python program for implementation of MergeSort
6+
7+
# Merges two subarrays of arr[].
8+
# First subarray is arr[l..m]
9+
# Second subarray is arr[m+1..r]
10+
def merge(arr, l, m, r):
11+
n1 = m - l + 1
12+
n2 = r- m
13+
14+
# create temp arrays
15+
L = [0] * (n1)
16+
R = [0] * (n2)
17+
18+
# Copy data to temp arrays L[] and R[]
19+
for i in range(0 , n1):
20+
L[i] = arr[l + i]
21+
22+
for j in range(0 , n2):
23+
R[j] = arr[m + 1 + j]
24+
25+
# Merge the temp arrays back into arr[l..r]
26+
i = 0 # Initial index of first subarray
27+
j = 0 # Initial index of second subarray
28+
k = l # Initial index of merged subarray
29+
30+
while i < n1 and j < n2 :
31+
if L[i] <= R[j]:
32+
arr[k] = L[i]
33+
i += 1
34+
else:
35+
arr[k] = R[j]
36+
j += 1
37+
k += 1
38+
39+
# Copy the remaining elements of L[], if there
40+
# are any
41+
while i < n1:
42+
arr[k] = L[i]
43+
i += 1
44+
k += 1
45+
46+
# Copy the remaining elements of R[], if there
47+
# are any
48+
while j < n2:
49+
arr[k] = R[j]
50+
j += 1
51+
k += 1
52+
53+
# l is for left index and r is right index of the
54+
# sub-array of arr to be sorted
55+
def mergeSort(arr,l,r):
56+
if l < r:
57+
58+
# Same as (l+r)//2, but avoids overflow for
59+
# large l and h
60+
m = (l+(r-1))//2
61+
62+
# Sort first and second halves
63+
mergeSort(arr, l, m)
64+
mergeSort(arr, m+1, r)
65+
merge(arr, l, m, r)
66+
67+
68+
# Driver code to test above
69+
arr = [12, 11, 13, 5, 6, 7]
70+
n = len(arr)
71+
print ("Given array is")
72+
for i in range(n):
73+
print ("%d" %arr[i]),
74+
75+
mergeSort(arr,0,n-1)
76+
print ("\n\nSorted array is")
77+
for i in range(n):
78+
print ("%d" %arr[i]),

‎sortmerge.py‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#https://www.facebook.com/permalink.php?story_fbid=2830418890577388&id=100008279138695
2+
#Subscribed by Code House
3+
4+
5+
# Python program for implementation of MergeSort
6+
7+
# Merges two subarrays of arr[].
8+
# First subarray is arr[l..m]
9+
# Second subarray is arr[m+1..r]
10+
def merge(arr, l, m, r):
11+
n1 = m - l + 1
12+
n2 = r- m
13+
14+
# create temp arrays
15+
L = [0] * (n1)
16+
R = [0] * (n2)
17+
18+
# Copy data to temp arrays L[] and R[]
19+
for i in range(0 , n1):
20+
L[i] = arr[l + i]
21+
22+
for j in range(0 , n2):
23+
R[j] = arr[m + 1 + j]
24+
25+
# Merge the temp arrays back into arr[l..r]
26+
i = 0 # Initial index of first subarray
27+
j = 0 # Initial index of second subarray
28+
k = l # Initial index of merged subarray
29+
30+
while i < n1 and j < n2 :
31+
if L[i] <= R[j]:
32+
arr[k] = L[i]
33+
i += 1
34+
else:
35+
arr[k] = R[j]
36+
j += 1
37+
k += 1
38+
39+
# Copy the remaining elements of L[], if there
40+
# are any
41+
while i < n1:
42+
arr[k] = L[i]
43+
i += 1
44+
k += 1
45+
46+
# Copy the remaining elements of R[], if there
47+
# are any
48+
while j < n2:
49+
arr[k] = R[j]
50+
j += 1
51+
k += 1
52+
53+
# l is for left index and r is right index of the
54+
# sub-array of arr to be sorted
55+
def mergeSort(arr,l,r):
56+
if l < r:
57+
58+
# Same as (l+r)//2, but avoids overflow for
59+
# large l and h
60+
m = (l+(r-1))//2
61+
62+
# Sort first and second halves
63+
mergeSort(arr, l, m)
64+
mergeSort(arr, m+1, r)
65+
merge(arr, l, m, r)
66+
67+
68+
# Driver code to test above
69+
arr = [12, 11, 13, 5, 6, 7]
70+
n = len(arr)
71+
print ("Given array is")
72+
for i in range(n):
73+
print ("%d" %arr[i]),
74+
75+
mergeSort(arr,0,n-1)
76+
print ("\n\nSorted array is")
77+
for i in range(n):
78+
print ("%d" %arr[i]),

0 commit comments

Comments
 (0)