472,353 Members | 2,037 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 2185
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.

### Similar topics

 1 by: Jochus | last post by: Today, I've programmed Mergesort. And it works very good :-)! But now, the teacher said that you could use Mergesort to count the amount of... 1 by: Jamal | last post by: I am working on binary files of struct ACTIONS I have a recursive qsort/mergesort hybrid that 1) i'm not a 100% sure works correctly 2) would... 6 by: Jamal | last post by: I am working on binary files of struct ACTIONS I have a recursive qsort/mergesort hybrid that 1) i'm not a 100% sure works correctly 2) would... 2 by: rkk | last post by: Hi, My mergesort program is below. There is a small piece of logical error/bug in this code which I can't figure out, as a result the output... 51 by: Joerg Schoen | last post by: Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was... 5 by: Chad | last post by: I was looking at some old posts in comp.lang.c and found the following ... 1 by: Kemmylinns12 | last post by: Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and... 0 by: jalbright99669 | last post by: Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made... 0 by: antdb | last post by: Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was... 0 by: Matthew3360 | last post by: Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ... 2 by: Matthew3360 | last post by: Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it... 0 by: AndyPSV | last post by: HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable... 0 by: Arjunsri | last post by: I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and... 0 by: Oralloy | last post by: Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the... 0 by: BLUEPANDA | last post by: At BluePanda Dev, we're passionate about building high-quality software and sharing our knowledge with the community. That's why we've created a SaaS...