[Javascript] マージソートプログラム

[kanata0404]

[至急] 以下の問題が分かりません。提出期限が明日までなので手助けお願いします！

[問題]
マージソートの変形版として，以下のようなアルゴリズムを実現せ
よ．プログラムは数のリスト lstを引数として，与えると以下のアル
ゴリズムでソートした列を返すものとする．実現する関数はkadai
(lst)として定義せよ．

1. キューにlstのそれぞれの要素を個別にリストにしてそれぞ
れ入れておく．
2. キューの長さが2以上である間以下の動作を繰り返す：
キューから２つ要素を取り出して，その2つの要素を
マージし，結果をキューに付け加える．
3. キューの唯一の要素を結果として返す．

マージソートのプログラムは以下の通りです。

コード:

function merge(lst1, lst2){
var lst = []
while (true){
if (lst1.length == 0) return lst.concat(lst2)
else if (lst2.length == 0) return lst.concat(lst1)
if (lst1[0] < lst2[0]) lst.push(lst1.shift())
else lst.push(lst2.shift())
}
}

function msort(lst){
var n = lst.length
if (n < 2) return lst
else {
var n2 = Math.floor(n / 2)
return merge(
msort(lst.slice(0, n2)), msort(lst.slice(n2, n)))
}
}
m = [7,3,5,4,1,2,4]
puts(m)
puts(msort(m))

申し訳ないのですが、期限が明日までなので、できればプログラム自体を教えて欲しいです。
ちなみに、実行環境は学校のホームページのものを使っています。

ちなみに、完成すると以下のような出力になるみたいです。
[出力結果]
7,3,5,4,1,2,4
3,7
4,5
1,2
4
1,2,3,4,4,5,7

[みけCAT]

何か自分で努力はしましたか？

1. 自分は今何がしたくて

2. どう取り組んで(作ったプログラムはどれで

3. どのようなエラーやトラブルで困っていて

4. 自分は何が解らないのか、知りたいのか

5. 今のＣの知識はどの程度なのか

この５点をしっかりと明記して下さい。

(フォーラムルールより転載)

5番は今回はCではなくJavaScriptですね。

[kanata]

1.
プログラムを完成させたいです。
2.
最初に掲示したマージソートプログラムは自分で作りました。（ほとんど調べたものではありますが）
3.
エラー、トラブルは特にないですが、現状のプログラムは以下のような出力になってしまいます。
[出力結果]
7,3,5,4,1,2,4
1,2,3,4,4,5,7
4.
何がというより全てわからないです
5.
完全な初心者であり、資料等を見てもほとんど分かりません。（このプログラム文があるからこういう結果になるとかがよくわかりません。）

[かずま]

問題の指示に従って書いてみました。
実行結果の表示は質問に従っていません。

コード:

<script>
function puts(x) { document.write(x + "</br>") }

function merge(lst1, lst2) {
    var lst = []
    while (true) {
        if (lst1.length == 0)
            return lst.concat(lst2)
        if (lst2.length == 0)
            return lst.concat(lst1)
        if (lst1[0] < lst2[0])
            lst.push(lst1.shift())
        else
            lst.push(lst2.shift())
    }
}

function kadai(lst) {
    var que = []
    for (i = 0; i < lst.length; i++)  // 1. lstのそれぞれの要素を個別に
        que.push([lst[i]])            //    リストにして que に入れる
    while (que.length >= 2) {     // 2. queの長さが 2以上である間
        var tmp = []                  //    一時的キュー
        while (que.length >= 2)       //    queから 2つの要素を取り出して
            tmp.push(merge(que.shift(), que.shift()))  // マージしてキューに
        if (que.length > 0)           //    1つ要素が残れば
            tmp.push(que.shift())     //    キューに入れる
        puts("---")
        for (i = 0; i < tmp.length; i++)
            puts(tmp[i])
        que = tmp                     //    繰り返す
    }
    puts("===")
    return que[0]                 // 3. キューの唯一の要素を結果として返す
}

m = [7,3,5,4,1,2,4]
puts(m)
puts(kadai(m))
</script>

実行結果

コード:

7,3,5,4,1,2,4
---
3,7
4,5
1,2
4
---
3,4,5,7
1,2,4
---
1,2,3,4,4,5,7
===
1,2,3,4,4,5,7

[かずま]

すみません。"</br>" は間違いです。
"<br/>" または "<br>" に訂正します。
でも、Google Chrome では動いていました。

[kanata]

お礼を言うのが遅れて申し訳ありません。
かずまさんのおかげでなんとか完成しました。
ありがとうございました！m(_ _)m

[kanata]

解決！にチェックを入れ忘れてました。