; sortiere-durch-mischen.scm
;                             (require (lib "breakpoint.ss"))
; ----- Hilfsfunktion: mische-sortierte-listen ------
(define
  (mische-sortierte-listen erste zweite)
  (cond
    ((null? erste)
     zweite)
    ((null? zweite)
     erste)
    ((< (car erste) (car zweite))
     (cons (car erste) (mische-sortierte-listen (cdr erste) zweite)))
    (else
     (cons (car zweite) (mische-sortierte-listen erste (cdr zweite)))))
  )

; ----- Hilfsfunktion spalte -----
(define
  (spalte liste erste zweite)
  (cond
    ((null? liste)
     (cons erste zweite))
    ((null? (cdr liste))
     (cons (cons (car liste) erste) zweite))
    (else
     (spalte (cddr liste) (cons (car liste) erste) (cons (cadr liste) zweite))))
  )

;;; ===== sortiere =====
; mischt die sortierten gespaltenen Listen;
; durch die fehlende Zwischenspeicherung ist ein doppelter Aufruf von spalte
; notwendig.
(define
  (sortiere liste)
  (if
   (or (null? liste) (null? (cdr liste)))
   liste
   (mische-sortierte-listen 
    (sortiere (car (spalte liste '() '())))
    (sortiere (cdr (spalte liste '() '())))
    )))
; Test: (sortiere '(54 564 7647 8659 449 864 36 989 56 9 9 6 97 6))
; Test mit großer Datei: 
(define
  (erzeuge-zufalls-zahlen n)
  (random-seed (current-milliseconds))
  (let whlg ((n n) (liste '()))
    (if (zero? n) liste (whlg (- n 1) (cons (random 4294967087) liste)))))
(define ergebnis (sortiere (erzeuge-zufalls-zahlen 100000)))