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) '() '())))))
