I was reading about merge sort(In place) in my algorithm book (Intro to algorithms 3rd edition Cormen), and I decided to implement it in Python. The problem is that I can't find what I am doing wrong... I saw some code in C++, but even with that I can't fix it.
Here is my code:
def MERGE(A,start,mid,end):
L=[0]*(mid - start + 1)
for i in range(len(L) - 1):
L[i] = A[start+i]
L[len(L) - 1] = 100000 # centinel, (fix)
R=[0]*(end - mid + 2)
for j in range(len(R) - 1):
R[j] = A[mid+j]
R[len(R) - 1] = 100000
i = 0
j = 0
k = start
for l in range(k,end):
if(L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[k] = R[j]
j = j + 1
def mergeSort(A,p,r):
if p < r:
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid+1,r)
MERGE(A,p,mid,r)
A = [20, 30, 15, 21, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)]
When I run the code I have some index problems:
File "myrealmerge.py", line 9, in MERGE
R[j] = A[mid+j]
IndexError: list index out of range
I know that this my be a "dumb question" and that there is some related post, but I tried the suggestions in there and It does not work for me...
Can anyone help me? T
Thanks!
This code works fine:
def MERGE(A,start,mid,end):
L = A[start:mid]
R = A[mid:end]
i = 0
j = 0
k = start
for l in range(k,end):
if j >= len(R) or (i < len(L) and L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[l] = R[j]
j = j + 1
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid,r)
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
print A
I tried to minimize the change from your code.
Good luck!
(Added)
You can check the dividing process by using this code.
def MERGE(A,start,mid,end):
# Do nothing
pass
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
print A[p:mid],A[mid:r]
mergeSort(A,p,mid)
mergeSort(A,mid,r)
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
The result is as follows:
[20, 30, 21, 15] [42, 45, 31, 0, 9]
[20, 30] [21, 15]
[20] [30]
[21] [15]
[42, 45] [31, 0, 9]
[42] [45]
[31] [0, 9]
[0] [9]
This is what we want. However, 'mid+1' makes invalid result. Here is the test code:
def MERGE(A,start,mid,end):
# Do nothing
pass
def mergeSort(A,p,r):
if r - p > 1:
mid = int((p+r)/2)
print A[p:mid],A[mid+1:r] # Changed
mergeSort(A,p,mid)
mergeSort(A,mid+1,r) # Changed
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A))
result:
[20, 30, 21, 15] [45, 31, 0, 9]
[20, 30] [15]
[20] []
[45, 31] [9]
[45] []
(Added)
Here is a code using 'mid+1':
# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
return origin_list[left_index:right_index+1]
def MERGE(A,start,mid,end):
L = get_partial_list(A,start,mid)
R = get_partial_list(A,mid+1,end)
i = 0
j = 0
k = start
for l in range(k,end+1): # changed
if j >= len(R) or (i < len(L) and L[i] < R[j]):
A[l] = L[i]
i = i + 1
else:
A[l] = R[j]
j = j + 1
def mergeSort(A,p,r):
if r - p > 0: # changed
mid = int((p+r)/2)
mergeSort(A,p,mid)
mergeSort(A,mid+1,r) # changed
MERGE(A,p,mid,r)
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1) # changed
print A
I've added new indexing function. Is this the code you expected?
Recursively split the array into left and right part and then merge it as per your requirements i.e ASC or DESC, Check the below code:
def merge_sort(a):
if len(a) <= 1:
return a
left = [];
right = [];
mid = len(a)/2
left = a[0:mid]
right = a[mid:(len(a))]
print left
print right
#exit()
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
while len(left) > 0 and len(right) > 0:
lv = left[0]
rv = right[0]
if lv <= rv:
result.append(lv)
left.pop(0)
else:
result.append(rv)
right.pop(0)
while len(left) > 0:
result.append(left.pop(0))
while len(right) > 0:
result.append(right.pop(0))
return result
A = [20, 30, 21, 15, 42, 45, 31, 0, 9]
print A
print merge_sort(A)
For understanding I have printed the intermediate partitioned array have a look into the output:
[20, 30, 21, 15, 42, 45, 31, 0, 9]
[20, 30, 21, 15]
[42, 45, 31, 0, 9]
[20, 30]
[21, 15]
[20]
[30]
[21]
[15]
[42, 45]
[31, 0, 9]
[42]
[45]
[31]
[0, 9]
[0]
[9]
[0, 9, 15, 20, 21, 30, 31, 42, 45]
Hope this will help you to understand the logic.
The solutions provided by lancif and krishna Prasad dont not have space complexity O(1).
Here is algorithm in place merge sorting for Py3 with space complexity O(1).
The main function sort_imerge uses 2 auxiliary functions wmerge and wsort.
This solution based on C code that discussed on:
other SO topic and on good C implementation
Also you can find full Python code with doctests here
def sort_imerge(Seq, l=0, u=None):
""" Merge sorting, mutable input.
Input sequence changed in place.
Time: O(n * log n)
log n -- levels
n -- elements on each level must be merged
Space (additional): O(1)
input changed in place
Returns None
"""
u = len(Seq) if u is None else u
if u - l > 1:
m = l + (u - l) // 2
w = l + u - m
wsort(Seq, l, m, w)
while w - l > 2:
n = w
w = l + (n - l + 1) // 2
wsort(Seq, w, n, l)
wmerge(Seq, l, l + n - w, n, u, w)
n = w
while n > l: # fallback to insert sort
for m in range(n, u):
if Seq[m-1] > Seq[m]:
Seq[m-1], Seq[m] = Seq[m], Seq[m-1]
n -= 1
def wmerge(Seq, i, m, j, n, w):
"""Merge subarrays [i, m) and [j, n) into work area w.
All indexes point into Seq.
The space after w must be enough to fit both subarrays.
"""
while i < m and j < n:
if Seq[i] < Seq[j]:
Seq[i], Seq[w] = Seq[w], Seq[i]
i += 1
else:
Seq[j], Seq[w] = Seq[w], Seq[j]
j += 1
w += 1
while i < m:
Seq[i], Seq[w] = Seq[w], Seq[i]
i += 1
w += 1
while j < n:
Seq[j], Seq[w] = Seq[w], Seq[j]
j += 1
w += 1
def wsort(Seq, l, u, w):
"""Sort subarray [l, u) and put reuslt into work area w.
All indexes point into Seq.
"""
if u - l > 1:
m = l + (u - l) // 2
sort_imerge(Seq, l, m)
sort_imerge(Seq, m, u)
wmerge(Seq, l, m, m, u, w)
else:
while l < u:
Seq[l], Seq[w] = Seq[w], Seq[l]
l +=1
w +=1
