Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 3x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 51x 6x 6x 45x 51x 19x 19x 19x 45x 51x 169x 169x 1296x 1296x 1296x 1296x 1296x 1296x 57x 57x 1296x 1296x 1296x 1296x 4662x 4662x 4662x 4662x 1296x 1296x 1296x 1296x 1296x 1296x 1296x 6580x 6580x 6580x 6580x 6580x 2545x 2545x 2545x 6580x 4035x 4035x 4035x 4035x 6580x 6580x 1296x 1296x 627x 627x 627x 627x 627x 1296x 169x 45x 51x 3x 3x 3x 3x 3x | /**
* @license Apache-2.0
*
* Copyright (c) 2026 The Stdlib Authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
'use strict';
// MODULES //
var isPositiveZero = require( '@stdlib/math/base/assert/is-positive-zero' );
var isNegativeZero = require( '@stdlib/math/base/assert/is-negative-zero' );
var isnan = require( '@stdlib/math/base/assert/is-nan' );
// MAIN //
/**
* Sorts a double-precision floating-point strided array using merge sort.
*
* ## Notes
*
* - This implementation uses a bottom-up iterative merge sort which requires a workspace array having at least `N` indexed elements.
*
* @param {PositiveInteger} N - number of indexed elements
* @param {number} order - sort order
* @param {Float64Array} x - input array
* @param {integer} strideX - stride length for `x`
* @param {NonNegativeInteger} offsetX - starting index for `x`
* @param {Float64Array} workspace - workspace array
* @param {integer} strideW - stride length for `workspace`
* @param {NonNegativeInteger} offsetW - starting index for `workspace`
* @returns {Float64Array} input array
*
* @example
* var Float64Array = require( '@stdlib/array/float64' );
*
* var x = new Float64Array( [ 1.0, -2.0, 3.0, -4.0 ] );
* var workspace = new Float64Array( x.length );
*
* dsortmg( x.length, 1.0, x, 1, 0, workspace, 1, 0 );
* // x => <Float64Array>[ -4.0, -2.0, 1.0, 3.0 ]
*/
function dsortmg( N, order, x, strideX, offsetX, workspace, strideW, offsetW ) {
var mid;
var v1;
var v2;
var hi;
var lo;
var ix;
var iw;
var jx;
var kx;
var i;
var j;
var w;
if ( N <= 0 || order === 0.0 ) {
return x;
}
// For a positive stride, sorting in decreasing order is equivalent to providing a negative stride and sorting in increasing order, and, for a negative stride, sorting in decreasing order is equivalent to providing a positive stride and sorting in increasing order...
if ( order < 0.0 ) {
strideX *= -1;
offsetX -= (N-1) * strideX;
}
// Iteratively merge adjacent runs of doubling width until the array is sorted...
for ( w = 1; w < N; w *= 2 ) {
// Merge adjacent pairs of runs...
for ( lo = 0; lo < N-w; lo += 2*w ) {
// Compute the index separating the "left" and "right" runs:
mid = lo + w;
// Compute the (exclusive) end index of the "right" run, being careful to avoid exceeding array bounds:
hi = mid + w;
if ( hi > N ) {
hi = N;
}
// Copy the "left" run to the workspace array in order to make room for merged elements:
ix = offsetX + (lo*strideX);
iw = offsetW;
for ( i = 0; i < w; i++ ) {
workspace[ iw ] = x[ ix ];
ix += strideX;
iw += strideW;
}
// Merge the runs...
i = 0;
j = mid;
iw = offsetW;
jx = offsetX + (j*strideX);
kx = offsetX + (lo*strideX);
while ( i < w && j < hi ) {
v1 = workspace[ iw ];
v2 = x[ jx ];
// Take from the "right" run only when its next value is strictly "less" than the next value of the "left" run, thus ensuring sort stability...
if ( v2 < v1 || ( isnan( v1 ) && !isnan( v2 ) ) || ( v1 === v2 && isNegativeZero( v2 ) && isPositiveZero( v1 ) ) ) { // eslint-disable-line max-len
x[ kx ] = v2;
j += 1;
jx += strideX;
} else {
x[ kx ] = v1;
i += 1;
iw += strideW;
}
kx += strideX;
}
// Copy any remaining "left" run elements (any remaining "right" run elements are already in place):
while ( i < w ) {
x[ kx ] = workspace[ iw ];
i += 1;
iw += strideW;
kx += strideX;
}
}
}
return x;
}
// EXPORTS //
module.exports = dsortmg;
|