I have written this code to sort a list of numbers, in increasing order.

It is a combination of quick sort, insertion sort, and merge sort. I make the first element of the list a pivot, then I go through the list. If a number is less than or equal to the pivot, I "insert" the number in its appropriate position in the left list. Otherwise, it is inserted into right list. After I reach the end of the list I simply merge the left and right lists, since they are already sorted.

I would like to know the time complexity of this sorting method. I believe the best case scenario is \$O(n)\$. What would be the average time?

#lang racket

(define (merge-lists l1 l2)
  (cond ((null? l1) l2)
        ((null? l2) l1)
        ((<= (car l1) (car l2))
         (cons (car l1) (merge-lists (cdr l1) l2)))
         (cons (car l2) (merge-lists l1 (cdr l2))))))

(define (insert elem lst)
  (if (or (null? lst) (<= elem (car lst)))
      (cons elem lst)
      (cons (car lst) (insert elem (cdr lst)))))

(define (quick-sorter lst)
  (if (null? lst)
      (let ((pivot (car lst)))
         (letrec ((iter (lambda (l left-l right-l)
                          (cond ((null? l)
                                 (merge-lists left-l right-l))
                                ((<= (car l) pivot)
                                 (iter (cdr l) (insert (car l) left-l) right-l))
                                 (iter (cdr l) left-l (insert (car l) right-l)))))))
           (iter (cdr lst) '() '())))))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.