MergeSort

[ben81]

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)

[Steven D'Aprano]

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