[plt-scheme] Mergesort - HTDP 26.1.2

From: wooks . (wookiz at hotmail.com)
Date: Tue Jul 25 22:27:37 EDT 2006

Is this mergesort algorithm given for this problem asymptotically equivalent 
to the more traditional top down one that proceeds by repeatedly halving the 
input and then merging.

My initial gut feel was that it wasn't but thinking about it a little 
harder, isn't it the case that we are doing the same amount of work in 
reverse order.

P.S. Was the intended output of the algorithm a nested list as opposed to a 
list?




Posted on the users mailing list.