schemeがモテないわけ

merge sortを書いてみた

http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html

O(N*log(N))の計算量が保障されるアルゴリズムで
quick sortより平均時間が安定しているらしい

参考先にjava版があったので引用すると
こんな感じになるらしい

  /*
   * マージ
   * 2つの配列a1[]とa2[]を併合してa[]を作ります。
   */
  void merge(int[] a1,int[] a2,int[] a){
    int i=0,j=0;
    while(i<a1.length || j<a2.length){
      if(j>=a2.length || (i<a1.length && a1[i]<a2[j])){
	a[i+j]=a1[i];
	i++;
      }
      else{
	a[i+j]=a2[j];
	j++;
      }
    }
  }

  /*
   * マージソート
   * 既にソート済みの2つの配列を併合して新しい配列を
   * 生成することで、データのソートを行います。
   */
  void mergeSort(int[] a){
    if(a.length>1){
      int m=a.length/2;
      int n=a.length-m;
      int[] a1=new int[m];
      int[] a2=new int[n];
      for(int i=0;i<m;i++) a1[i]=a[i];
      for(int i=0;i<n;i++) a2[i]=a[m+i];
      mergeSort(a1);
      mergeSort(a2);
      merge(a1,a2,a);
    }
  }

  /*
   * ソート
   */
  public void sort(int[] a){
    mergeSort(a);
  }

良く使われる配列なんかを主軸にするあたり
初心者向けにわかりやすい例だ

このjava版を受けてschemeでマージソートを書いてみた
コストが高くつくlength等を除去したら以下のようなコードが出来上がった

(define (merge xs ys)
  (cond
    ((and (pair? xs) (pair? ys))
     (if (< (car xs) (car ys))
         (cons (car xs)
               (marge (cdr xs) ys))
         (cons (car ys)
               (marge xs (cdr ys))))
    ((pair? xs) xs)
    (else ys)))

(define (merge-sort xs)
  (let part((base xs)
            (xs '())
            (ys '()))
    (if (null? base)
        (merge (merge-sort xs)
               (merge-sort ys))
        (part (cdr base)
              (cons (car base)
                    ys)
              xs))))

(define sort merge-sort)

自分で書いておいてアレだが
黒魔術という言葉が思い浮かんだ

自分で書く分には楽しいんだけど
人に勧められるかというとダメかもわかんね