title: Can I implement quicksort efficiently with Scheme?
body: <p>This is what I've done:</p>
  
  <pre><code>(define qsort
    (lambda (l)
      (let ((lesser '()))
        (let ((greater '()))
          (cond
            ((null? l) '())
            (else (map (lambda (ele)
                         (if (&gt; (car l) ele)
                             (set! lesser (cons ele lesser))
                             (set! greater (cons ele greater)))) (cdr l))
                  (append (qsort lesser) (cons (car l) (qsort greater))))
          )))))
  </code></pre>
  
  <p>I noticed that when provided with an already sorted list, it becomes extremely sluggish.
  After some searching, I found that if the "pivot" is selected in a random manner, the performance can be improved. 
  However the only way I know to achieve this is by <code>list-ref</code>, and it seems to be O(n).
  To make matters even worse, I have to implement a <code>cdr</code>-like function to remove n-th element in the list, which might also be extremely inefficient.</p>
  
  <p>Maybe I'm in the wrong direction. Could you give me some advice?</p>