Mergesort in Python optimization
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
2
down vote
favorite
I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster but I am open to suggestions in terms of optimization.
def merge(left,right):
sortedArray=
l_idx,r_idx=0,0 #set index for left and right array
#compare values of left and right array
while l_idx<len(left) and r_idx<len(right):
if(left[l_idx] < right[r_idx]):
sortedArray.append(left[l_idx])
l_idx+=1
else:
sortedArray.append(right[r_idx])
r_idx+=1
if l_idx==len(left):
sortedArray.extend(right[r_idx:])
else:
sortedArray.extend(left[l_idx:])
return sortedArray
def mergesort(A):
if len(A)<=1:
return A
middle=len(A)//2
left,right=mergesort(A[:middle]),mergesort(A[middle:])
return merge(left,right)
Thank you for any feedback
python sorting mergesort
asked Jun 23 at 12:22
Michael D
162
add a comment |Â
up vote
2
down vote
favorite
I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster but I am open to suggestions in terms of optimization.
def merge(left,right):
sortedArray=
l_idx,r_idx=0,0 #set index for left and right array
#compare values of left and right array
while l_idx<len(left) and r_idx<len(right):
if(left[l_idx] < right[r_idx]):
sortedArray.append(left[l_idx])
l_idx+=1
else:
sortedArray.append(right[r_idx])
r_idx+=1
if l_idx==len(left):
sortedArray.extend(right[r_idx:])
else:
sortedArray.extend(left[l_idx:])
return sortedArray
def mergesort(A):
if len(A)<=1:
return A
middle=len(A)//2
left,right=mergesort(A[:middle]),mergesort(A[middle:])
return merge(left,right)
Thank you for any feedback
python sorting mergesort
asked Jun 23 at 12:22
Michael D
162
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster but I am open to suggestions in terms of optimization.
def merge(left,right):
sortedArray=
l_idx,r_idx=0,0 #set index for left and right array
#compare values of left and right array
while l_idx<len(left) and r_idx<len(right):
if(left[l_idx] < right[r_idx]):
sortedArray.append(left[l_idx])
l_idx+=1
else:
sortedArray.append(right[r_idx])
r_idx+=1
if l_idx==len(left):
sortedArray.extend(right[r_idx:])
else:
sortedArray.extend(left[l_idx:])
return sortedArray
def mergesort(A):
if len(A)<=1:
return A
middle=len(A)//2
left,right=mergesort(A[:middle]),mergesort(A[middle:])
return merge(left,right)
Thank you for any feedback
python sorting mergesort
asked Jun 23 at 12:22
Michael D
162
I am currently writing mergesort in Python and have implemented it to work. I have noticed, though, that it is very slow compared to the standard sorted() method. I understand it will always be faster but I am open to suggestions in terms of optimization.
def merge(left,right):
sortedArray=
l_idx,r_idx=0,0 #set index for left and right array
#compare values of left and right array
while l_idx<len(left) and r_idx<len(right):
if(left[l_idx] < right[r_idx]):
sortedArray.append(left[l_idx])
l_idx+=1
else:
sortedArray.append(right[r_idx])
r_idx+=1
if l_idx==len(left):
sortedArray.extend(right[r_idx:])
else:
sortedArray.extend(left[l_idx:])
return sortedArray
def mergesort(A):
if len(A)<=1:
return A
middle=len(A)//2
left,right=mergesort(A[:middle]),mergesort(A[middle:])
return merge(left,right)
Thank you for any feedback
python sorting mergesort
asked Jun 23 at 12:22
Michael D
162
edited Jun 23 at 13:12
asked Jun 23 at 12:22
Michael D
162
asked Jun 23 at 12:22
Michael D
162
asked Jun 23 at 12:22
Michael D
162
162
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f197118%2fmergesort-in-python-optimization%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password