469,160 Members | 2,033 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,160 developers. It's quick & easy.

MergeSort

Hi,

the following code is adopted PseudoCode from Introduction to
Algorithms (Cormen et al). For some reason it can't get it to work. I
always get a index of out bounds exception or some weird result.
Secondly I'd like to know how to write this more pythonic. TIA.

import random
import listutil
import unittest

def merge(A, p, q, r):
L = A[p:q]
R = A[q+1:r]
L.append(1001)
R.append(1001)

i=0
j=0
k=p
for k in range(r-p+1):

if L[i] <= R[j]:
A[k] = L[i]
i +=1
else:
A[k] = R[j]
j +=1

def mergeSort(A,p,r):
if p < r:
q=(p+r)/2
mergeSort(A,p,q)
mergeSort(A,q+1,r)
merge(A,p,q,r)

Aug 9 '06 #1
1 2107
On Wed, 09 Aug 2006 12:50:11 -0700, ben81 wrote:
Hi,

the following code is adopted PseudoCode from Introduction to
Algorithms (Cormen et al).
I'm assuming you are doing this as a learning exercise, because -- trust
me on this -- nothing you write in pure Python code will come within cooee
of the speed of Python's build-in sort method.
For some reason it can't get it to work. I
always get a index of out bounds exception or some weird result.
No, don't tell us what the weird result is. I love to guess!

Is it this?

ImportError: No module named listutil
Not that it matters, because listutil doesn't seem to be used in your code.

Secondly I'd like to know how to write this more pythonic. TIA.
Document your code. Don't assume the reader will remember all the
details of Merge Sort. I certainly don't. It will also help you understand
how the algorithm works, which then will help you see what your code is
doing that it shouldn't (such as trying to merge empty lists).

Why are you appending 1001 to both sub-lists?
--
Steven D'Aprano

Aug 10 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Jochus | last post: by
1 post views Thread by Jamal | last post: by
2 posts views Thread by rkk | last post: by
51 posts views Thread by Joerg Schoen | last post: by
1 post views Thread by Mortomer39 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.