← Back to branch summary

~holger-seelig/cobweb.js/trunk

« back to all changes in this revision

Viewing changes to src/standard/Math/Algorithms/MergeSort.js

  • Committer: Holger Seelig
  • Date: 2017-08-22 04:53:24 UTC
  • Revision ID: holger.seelig@yahoo.de-20170822045324-4of4xxgt79669gbt
Switched to npm.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/standard/Math/Algorithms/MergeSort.js
 
1
/* -*- Mode: JavaScript; coding: utf-8; tab-width: 3; indent-tabs-mode: tab; c-basic-offset: 3 -*-
 
2
 *******************************************************************************
 
3
 *
 
4
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 
5
 *
 
6
 * Copyright create3000, Scheffelstraße 31a, Leipzig, Germany 2011.
 
7
 *
 
8
 * All rights reserved. Holger Seelig <holger.seelig@yahoo.de>.
 
9
 *
 
10
 * The copyright notice above does not evidence any actual of intended
 
11
 * publication of such source code, and is an unpublished work by create3000.
 
12
 * This material contains CONFIDENTIAL INFORMATION that is the property of
 
13
 * create3000.
 
14
 *
 
15
 * No permission is granted to copy, distribute, or create derivative works from
 
16
 * the contents of this software, in whole or in part, without the prior written
 
17
 * permission of create3000.
 
18
 *
 
19
 * NON-MILITARY USE ONLY
 
20
 *
 
21
 * All create3000 software are effectively free software with a non-military use
 
22
 * restriction. It is free. Well commented source is provided. You may reuse the
 
23
 * source in any way you please with the exception anything that uses it must be
 
24
 * marked to indicate is contains 'non-military use only' components.
 
25
 *
 
26
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 
27
 *
 
28
 * Copyright 2015, 2016 Holger Seelig <holger.seelig@yahoo.de>.
 
29
 *
 
30
 * This file is part of the Cobweb Project.
 
31
 *
 
32
 * Cobweb is free software: you can redistribute it and/or modify it under the
 
33
 * terms of the GNU General Public License version 3 only, as published by the
 
34
 * Free Software Foundation.
 
35
 *
 
36
 * Cobweb is distributed in the hope that it will be useful, but WITHOUT ANY
 
37
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 
38
 * A PARTICULAR PURPOSE. See the GNU General Public License version 3 for more
 
39
 * details (a copy is included in the LICENSE file that accompanied this code).
 
40
 *
 
41
 * You should have received a copy of the GNU General Public License version 3
 
42
 * along with Cobweb.  If not, see <http://www.gnu.org/licenses/gpl.html> for a
 
43
 * copy of the GPLv3 License.
 
44
 *
 
45
 * For Silvio, Joy and Adi.
 
46
 *
 
47
 ******************************************************************************/
 
48
 
 
49
 
 
50
define (function ()
 
51
{
 
52
"use strict";
 
53
 
 
54
        function MergeSort (array, compare)
 
55
        {
 
56
                this .array     = array;
 
57
                this .auxiliary = [ ];
 
58
 
 
59
                if (compare)
 
60
                        this .compare = compare;
 
61
        }
 
62
 
 
63
        MergeSort .prototype =
 
64
        {
 
65
                compare: function (lhs, rhs)
 
66
                {
 
67
                        return lhs < rhs;
 
68
                },
 
69
                sort: function (first, last)
 
70
                {
 
71
                        this .mergeSort (first, last - 1);
 
72
                },
 
73
                mergeSort: function (lo, hi)
 
74
                {
 
75
                        if (lo < hi)
 
76
                        {
 
77
                                var m = (lo + hi) >>> 1;
 
78
                                this .mergeSort (lo, m);   // Recursion
 
79
                                this .mergeSort (m + 1, hi); // Recursion
 
80
                                this .merge (lo, m, hi);
 
81
                        }
 
82
                },
 
83
                merge: function (lo, m, hi)
 
84
                {
 
85
                        var i, j, k;
 
86
 
 
87
                        i = 0, j = lo;
 
88
                        // Copy first half of array a to auxiliary array b.
 
89
                        while (j <= m)
 
90
                                this .auxiliary [i++] = this .array [j++];
 
91
 
 
92
                        i = 0; k = lo;
 
93
                        // Copy back next-greatest element at each time.
 
94
                        while (k < j && j <= hi)
 
95
                        {
 
96
                                if (this .compare (this .array [j], this .auxiliary [i]))
 
97
                                        this .array [k++] = this .array [j++];
 
98
                                else
 
99
                                        this .array [k++] = this .auxiliary [i++];
 
100
                        }
 
101
 
 
102
                        // Copy back remaining elements of first half (if any).
 
103
                        while (k < j)
 
104
                                this .array [k++] = this .auxiliary [i++];
 
105
                }
 
106
        };
 
107
 
 
108
        return MergeSort;
 
109
});