Redundant computations in src/pkg/sort/sort.go

[gopherbot]

by Raphael.Geronimi:

Browsing through Golang code (a pleasure), I was surprised to see that in the case where
there are more than 7 items, the quicksort function calls BOTH a recursive quicksort
code and an insertion sort, instead of doing one OR the other (as one sees in many libs,
insertion sort having better performance on small lists).
This redundancy is compounded by the recursive nature of quicksort.
I am no expert in sorting algorithms so I may have missed something obvious, but it
seems a "else" is missing on line 184:
166 func quickSort(data Interface, a, b, maxDepth int) {
   167      for b-a > 7 {
   168          if maxDepth == 0 {
   169              heapSort(data, a, b)
   170              return
   171          }
   172          maxDepth--
   173          mlo, mhi := doPivot(data, a, b)
   174          // Avoiding recursion on the larger subproblem guarantees
   175          // a stack depth of at most lg(b-a).
   176          if mlo-a < b-mhi {
   177              quickSort(data, a, mlo, maxDepth)
   178              a = mhi // i.e., quickSort(data, mhi, b)
   179          } else {
   180              quickSort(data, mhi, b, maxDepth)
   181              b = mlo // i.e., quickSort(data, a, mlo)
   182          }
   183      }
   184      if b-a > 1 {
   185          insertionSort(data, a, b)
   186      }
   187  }

[minux]

Comment 1:

line 167 is a for loop, and it will terminate only when b - a <= 7,
and if we still haven't finished (i.e. when b - a > 1), it uses insertion
sort to finish the job.

Status changed to WorkingAsIntended.

[gopherbot]

Comment 2 by Raphael.Geronimi:

Right! The uniform syntax of Golang has bitten me, I confused the "for" with a "if" :)