JavaScriptAlgorithms/Sort/MergeSort Bottom.html at master · biaodigit/JavaScriptAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    function mergeSortBottom(arr) {
        let len = arr.length;
        for (let sz = 1; sz <= len; sz += sz) {
            for (let i = 0; i + sz <= len; i += sz + sz) {
                // 对arr[i...i+sz-1]和arr[i+sz.....i+2*sz-1]排序
                _merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, len - 1));
            }
        }
    }

    function _merge(arr, l, mid, r) {
        let aux = []
        for (let i = l; i <= r; i++) {
            aux[i - l] = arr[i]
        }

        let i = l,
            j = mid + 1;
        for (let k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = aux[j - l]
                j++
            } else if (j > r) {
                arr[k] = aux[i - l]
                i++
            } else if (aux[i - l] > aux[j - l]) {
                arr[k] = aux[j - l]
                j++
            } else {
                arr[k] = aux[i - l]
                i++
            }
        }
        console.log(arr)
    }

    mergeSortBottom([3, 1, 5, 7, 2, 4, 9, 6, 10, 8])
</script>
</body>
</html>