4
\$\begingroup\$

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)))
        (else
         (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))
                                (else
                                 (iter (cdr l) left-l (insert (car l) right-l)))))))
           (iter (cdr lst) '() '())))))
\$\endgroup\$

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.