## Problem : Timing sort performance

The following program puts together the insertion sort and merge sort algorithms. It also implements a function named sortTimer to measure how much time it takes to apply a sort algorithm to a random list of given size.

Extend this program to do the following:

1. Measure time performance of a given sort function for given random list size, repeated $$k$$ times, where $$k$$ is an additional parameter of your function. Take and return the average sorting time as the output of yopur function.
2. Do the above measurement for list sizes of 10, 100, 1000, and 10000, applied to both insertion sort and merge sort algorithms. Report, compare, and interpret the outcomes.

;;; CREATE RANDOM LIST
;Function n:number k:number -> list
;Returns a list of size n, containin random numbers each between 0 and k
(define (makeRandomList n k)
(cond
((or (< n 0) (< k 0)) (error "invalid input"))
((= n 0) empty)
(else (cons (random k) (makeRandomList (- n 1) k)))))

;;; INSERTION SORT
;Function number ascending-sorted-list -> sorted-list
;Returns a version of the list where the vlue is inserted in proper order
(define (insert value sortedList)
(cond
((empty? sortedList) (cons value empty))
((< value (first sortedList)) (cons value sortedList))
(else (cons (first sortedList) (insert value (rest sortedList))))))

;Function list ascending-sorted-list -> sorted-list
;returns a list obtained by inserting each of the values in the list into sorted list in proper order
(define (insertAll unsortedList sortedList)
(cond
((empty? unsortedList) sortedList)
(else
(insertAll
(rest unsortedList)
(insert (first unsortedList) sortedList)))))

(define (insertionSorter unsortedList)
(insertAll unsortedList empty))

;;;MERGE SORT
;Function that splits the given list into two equal size halves
(define (split list)
(splitAccumulator empty empty list))
;helper function
(define (splitAccumulator half1 half2 originalList)
(cond
((empty? originalList) (list half1 half2))
(else (splitAccumulator half2 (cons (first originalList) half1) (rest originalList)))))

(define (sortHalvesHelper halves)
(list (merge-sort (first halves)) (merge-sort (first (rest halves)))))

(define (mergeHalvesHelper halves)
(mergeHalves (first halves) (first (rest halves))))

(define (mergeHalves half1 half2)
(cond
((empty? half1) half2)
((empty? half2) half1)
((< (first half1) (first half2)) (cons (first half1) (mergeHalves (rest half1) half2)))
(else (cons (first half2) (mergeHalves half1 (rest half2))))))

(define (merge-sort unsorted)
(cond
((or (empty? unsorted) (empty? (rest unsorted))) unsorted)
(else (mergeHalvesHelper (sortHalvesHelper (split unsorted))))))
;;;TIMING
(define startTime void)
(define (sortTimer sortFunction length)
(begin
(set! startTime (current-milliseconds))
(sortFunction (makeRandomList length 1000))
(- (current-milliseconds) startTime)))

(sortTimer merge-sort 1000)
(sortTimer insertionSorter 1000)