I wrote merge sort in Scheme
(define (merge l1 l2)
(cond ((null? l1) l2)
((null? l2) l1)
((< (car l1) (car l2)) (cons (car l1) (merge (cdr l1) l2)))
(else (cons (car l2) (merge l1 (cdr l2))))))
(define (merge-sort l)
(cond ((null? l) '())
(else (merge (list (car l)) (merge-sort (cdr l))))))anon : write merge sort in scheme
ChatGPT :
Certainly! Here's an implementation of the merge sort algorithm in Scheme:
(define (merge-sort lst)
(if (<= (length lst) 1)
lst
(let* ((mid (quotient (length lst) 2))
(left (take lst mid))
(right (drop lst mid)))
(merge (merge-sort left) (merge-sort right)))))
(define (merge left right)
(cond ((null? left) right)
((null? right) left)
((< (car left) (car right)) (cons (car left) (merge (cdr left) right)))
(else (cons (car right) (merge left (cdr right))))))
(define (take lst n)
(if (= n 0)
'()
(cons (car lst) (take (cdr lst) (- n 1)))))
(define (drop lst n)
(if (= n 0)
lst
(drop (cdr lst) (- n 1))))
;; Example usage:
(define my-list '(5 1 4 2 8 7 3))
(display "Original List: ")
(display my-list)
(newline)
(display "Sorted List: ")
(display (merge-sort my-list))
(newline)This code defines the merge-sort function, which takes a list as input and sorts it using the merge sort algorithm. It also defines the helper functions merge, take, and drop to facilitate the sorting process.
Make sure to load this code into your Scheme interpreter or compiler to use it. You can replace my-list with your own list of numbers that you want to sort.
>>1
This is not a merge sort because you are not breaking the list in half
when you call merge:
merge (list (car l)) (merge-sort (cdr l)))))
Heres a merge sort I wrote where the merging and breaking are tail recursive
(define (merge-sort comparison lis)
(define (break fst snd tail)
(cond
((null? tail ) (cons fst snd))
((null? (cdr tail)) (cons (cons (car tail) fst) snd))
(else (break
(cons (car tail) fst)
(cons (cadr tail) snd)
(cddr tail)))))
(define (mix-rev fst snd acc orientation)
(cond
((and (null? fst) (null? snd)) acc)
((null? fst)
(mix-rev `() (cdr snd) (cons (car snd) acc) orientation))
((null? snd)
(mix-rev (cdr fst) `() (cons (car fst) acc) orientation))
((eq? orientation (comparison (car fst) (car snd)))
(mix-rev (cdr fst) snd (cons (car fst) acc) orientation))
(else
(mix-rev fst (cdr snd) (cons (car snd) acc) orientation))))
(define (oriented-sort lis orientation)
(cond
((null? lis) lis)
((null? (cdr lis)) lis)
((null? (cddr lis))
(if (eq? orientation (comparison (car lis) (cadr lis))) lis
(list (cadr lis) (car lis))))
(else (let ((rec (break `() `() lis)))
(mix-rev
(oriented-sort (car rec) (not orientation))
(oriented-sort (cdr rec) (not orientation))
`() (not orientation) )))))
(oriented-sort lis #t))>>3
It must be a novel algorithm then. Let's call it scheme-sort.
>>4
If you look closely at how its beeing sorted,
you can see its just an Insertion Sort
sorry :(
Can linked lists be sorted, effectively? It seems to me that no matter how it is done, it's just slow.
Very nice. Now let's see Paul Allen's merge sort.