# scheme Implementation of different sortings algorithms Merge Sort

## Example

Merge Sort is a common sorting algorithm with an average case complexity of `O(n log n)` and a worst case complexity of `O(n log n)`. Although it cannot be executed in-place, it guarantees `O(n log n)` complexity in all cases.

Merge Sort repeatedly splits the input in two, until an empty list or single-element list is reached. Having reached the bottom of the splitting tree, it then works its way back up, merging the two sorted splits into each other, until a single sorted list is left.

Using this, a Scheme implementation of Merge Sort may look like the following:

``````;; Merge two sorted lists into a single sorted list
(define (merge list1 list2)
(cond
((null? list1)
list2)
((null? list2)
list1)
(else
; Add the smaller element to the front of the merge list
(cons
; Recursively merge
(merge (cdr list1) list2))
(cons
; Recursively merge
(merge list1 (cdr list2))))))))

(define (split-list lst)
(let ((half (quotient (length lst) 2)))
; Create a pair of the first and second halves of the list
(cons
(take lst half)
(drop lst half))))

(define (merge-sort lst)
(cond
((or (null? lst) ; empty list is sorted, so merge up
(null? (cdr lst))) ; single-element list is sorted, so merge up
lst)
(else
(let ((halves (split-list lst)))
; Recursively split until the bottom, then merge back up to sort
(merge (merge-sort (car halves))
(merge-sort (cdr halves)))))))
`````` PDF - Download scheme for free