timsort-suite
Fri Aug 29 13:43:41Z 2025
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Fri Aug 29 13:43:41Z 2025
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Tests summary
((ran 9) (failed 0))
Here is a test suite for the timsort function, which implements the Timsort algorithm, a hybrid sorting algorithm derived from merge sort and insertion sort. It is designed to perform well on many kinds of real-world data. The implementation follows the specifications outlined in [1][2] that we extracted in [3] and we compare it against the built-in sort function [4][5]. For the sake of completeness, we report their implementation of the sort! function, which is a wrapper around the merge! function, which merges two sorted sequences. The sort! function sorts a sequence in place using a provided comparison function less?.
(define (sort! seq less?)
(define (step n)
(cond ((> n 2)
(let* ((j (quotient n 2)) (a (step j)) (k (- n j)) (b (step k)))
(merge! a b less?)))
((= n 2)
(let ((x (car seq)) (y (cadr seq)) (p seq))
(set! seq (cddr seq))
(if (less? y x) (begin (set-car! p y) (set-car! (cdr p) x)))
(set-cdr! (cdr p) '())
p))
((= n 1) (let ((p seq)) (set! seq (cdr seq)) (set-cdr! p '()) p))
(else '())))
(if (vector? seq)
(let ((n (vector-length seq)) (vec seq))
(set! seq (vector->list seq))
(do ((p (step n) (cdr p)) (i 0 (+ i 1)))
((null? p) vec)
(vector-set! vec i (car p))))
(step (length seq))))
(define (merge! a b less?)
(define (loop r a b)
(if (less? (car b) (car a))
(begin
(set-cdr! r b)
(if (null? (cdr b)) (set-cdr! b a) (loop b a (cdr b))))
(begin
(set-cdr! r a)
(if (null? (cdr a)) (set-cdr! a b) (loop a (cdr a) b)))))
(cond ((null? a) b)
((null? b) a)
((less? (car b) (car a))
(if (null? (cdr b)) (set-cdr! b a) (loop b a (cdr b)))
b)
(else (if (null? (cdr a)) (set-cdr! a b) (loop a (cdr a) b)) a)))
test/simple: pass(define (test/simple _)
(⊦= '(1 2 3 4 5) (timsort '(5 4 3 2 1)))
(⊦= '(1 2 3 4 5) (timsort '(1 2 3 4 5)))
(⊦= '(1 2 3 4 5) (timsort '(3 2 1 5 4)))
(⊦= '(1) (timsort '(1)))
(⊦= '() (timsort '())))
((eta 0.0) (memory #(50331648 24945128 1048576)) (stdout "") (stderr ""))
test/iota: passHere we test the timsort function with a large list of integers from 0 to 1000000 elements long. The list is sorted in descending order, and we expect the result to be a list sorted in ascending order.
(define (test/iota _) (⊦= r (timsort (iota n (sub1 n) -1))))
((eta 0.35) (memory #(100663296 48941800 1048576)) (stdout "") (stderr ""))
test/iota/sort: pass(define (test/iota/sort _) (⊦= r (sort (iota n (sub1 n) -1) <)))
((eta 0.331) (memory #(201326592 48942440 1048576)) (stdout "") (stderr ""))
test/timtros/iota: pass(define (test/timtros/iota _) (⊦= (iota n (sub1 n) -1) (timtros r)))
((eta 0.311) (memory #(201326592 72943144 1048576)) (stdout "") (stderr ""))
test/tros/iota: pass(define (test/tros/iota _) (⊦= (iota n (sub1 n) -1) (reverse (sort r <))))
((eta 0.299) (memory #(201326592 72943824 1048576)) (stdout "") (stderr ""))
test/already-sorted: pass(define (test/already-sorted _) (⊦= r (timsort r)))
((eta 0.411) (memory #(201326592 48944528 1048576)) (stdout "") (stderr ""))
test/already-sorted/sort: pass(define (test/already-sorted/sort _) (⊦= r (sort r <)))
((eta 0.287) (memory #(201326592 48945160 1048576)) (stdout "") (stderr ""))
test/already-sorted/primitive: pass(define (test/already-sorted/primitive _) (⊦= r (timsort/primitive r)))
((eta 0.123) (memory #(201326592 48945864 1048576)) (stdout "") (stderr ""))
test/primitive: pass(define (test/primitive _)
(⊦= (sort '(5 4 3 2 1) <) (timsort/primitive '(5 4 3 2 1)))
(⊦= '(hello world) (timsort/primitive '(world hello))))
((eta 0.0) (memory #(201326592 48946496 1048576)) (stdout "") (stderr ""))