473,554 Members | 3,055 Online

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 2234
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.
details of Merge Sort. I certainly don't. It will also help you understand
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 thread has been closed and replies have been disabled. Please start a new discussion.