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