1

I am a Tcl newbie and for the sake of learning I'm trying to implement a merge sort algorithm pseudo-code from Wikipedia:

function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
    return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)

In my Tcl script I do:

proc merge_sort { lst } {

   if { [llength $lst] <= 1 } {
       return $lst
   }

   set middle [expr {[llength $lst] / 2}]

   set left [lrange $lst 0 $middle]
   set right [lrange $lst [expr {$middle + 1}] [llength $lst]]

   set left [merge_sort $left]
   set right [merge_sort $right]

   return [merge $left $right]
}

According to my debug attempts, everything works fine until a recursive call of the merge_sort proc.

Output says that I am "out of stack space (infinite loop?)". Honestly, I don't see a problem in the code. Where am I wrong?

4

1 に答える 1

1

One problem is that your code uses [lrange $lst 0 $middle] to get the left part of the string, but since lrange's range is zero-based-inclusive it means that for a two-member list {7 8} you would get middle equals to 1 and left would be {7 8}.

Also since you are using [lrange $lst [expr {$middle + 1}] [llength $lst]] for right, than for the same list it would result in an empty list as [lrange $lst 2 2] is empty for a two-member list.

I've also changed the right lrange to use end as the last index as this is a common best practice instead of [expr {[llength $lst] - 1}] which would have been the equivalent.

proc merge_sort { lst } {

   if { [llength $lst] <= 1 } {
       return $lst
   }

   set middle [expr {[llength $lst] / 2}]

   #for each x in m *before* middle add x to left
   set left [lrange $lst 0 [expr {$middle - 1}]]

   #for each x in m *after or equal* middle add x to right
   set right [lrange $lst $middle end]

   set left [merge_sort $left]
   set right [merge_sort $right]

   return [merge $left $right]
}
于 2012-12-02T08:27:48.730 に答える