計算アルゴリズム

今度は大丈夫だと思います。updateは可読性のため末尾再帰にしてません。
それぞれの長さのリストを返します。たぶん 535と同じアルゴリズムだと思います。
550 は計算量 O(nlogn)なんでしょうか？

(define (update a ll)
  (cond ((null? (cadr ll)) (if (> a (car (car ll))) (cons (cons a '()) '(())) ll))
        ((<= a (car (cadr ll))) (cons (cons a (cadr ll)) (cdr ll)))
        (else (cons (car ll) (update a (cdr ll))))))

(define (search6 l)
  (cond ((null? l) '(()))
        ((null? (cdr l)) (cons (cons (car l) '()) '(())))
        (else
          (let ((ll (search6 (cdr l))))
            (let ((r (update (car l) (cons '() ll))))
              (if (null? (car r)) (cdr r) r))))))