algorithms-js/merge-sort.html at master · marcinvalas/algorithms-js · 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
<html>
    <head>
    </head>
    <body>
        <h1>merge sort</h1>
        <p id="values-to-sort"></p>
        <p id="sorted-values"></p>
        <p id="sorted-descending-values"></p>
    </body>

    <script>

        // O(n) where n = r - p + 1
        // p <= q < r
        // A[p..q] and A[q+1..r]
        function merge(A, p, q, r) {
            n1 = q - p + 1;
            n2 = r - q;
            var L = new Array(n1);
            var R = new Array(n2);

            for (var i = 0; i < n1; i++) {
                L[i] = A[p + i];
            }
            for (var i = 0; i < n2; i++) {
                R[i] = A[q + i + 1];
            }

            var i = 0;
            var j = 0;
            for (var a = p; a <= r; a++) {
                if (j >= n2) {
                    A[a] = L[i];
                    i += 1;
                } else if (i >= n1) {
                    A[a] = R[j];
                    j += 1;
                } else if (L[i] <= R[j]) {
                    A[a] = L[i];
                    i += 1;
                } else {
                    A[a] = R[j];
                    j += 1;
                }
            }

            return A;
        };


        var sss = [5, 8, 10, 1, 7, 9];
        var res = merge(sss, 0, 2, 5);

        function mergeSort(A, p, r) {
            if (p < r) {
                var q = Math.floor((p + r) / 2);
                mergeSort(A, p, q);
                mergeSort(A, q + 1, r);
                merge(A, p, q, r);
            }
        };


        var valuesToSort = [38, 27, 43, 3, 9, 82, 10];
		document.getElementById("values-to-sort").innerHTML = JSON.stringify(valuesToSort);

		var toSort = valuesToSort.slice();
		mergeSort(toSort, 0, toSort.length - 1);

		document.getElementById("sorted-values").innerHTML = JSON.stringify(toSort);

        //var sortedDescendingValues = insertionSortDescending(valuesToSort.slice());
        //document.getElementById("sorted-descending-values").innerHTML = JSON.stringify(sortedDescendingValues);

    </script>

</html>