Fast Stable Sorting Algorithm Implementation in JavaScript

Fast stable sorting algorithm implementation in javascript

It is possible to get a stable sorting from a non-stable sort function.

Before sorting you get the position of all the elements.
In your sort condition, if both elements are equal, then you sort by the position.

Tada! You've got a stable sort.

I've written an article about it on my blog if you want to know more about this technique and how to implement it: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Javascript Array.sort implementation?

I've just had a look at the WebKit (Chrome, Safari …) source. Depending on the type of array, different sort methods are used:

Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function std::qsort which implements some variation of quicksort (usually introsort).

Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or qsort if no merge sort is available.

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call “min” sort) or, in some cases, it sorts via an AVL tree. Unfortunately, the documentation here is rather vague so you’d have to trace the code paths to actually see for which types which sort method is used.

And then there are gems like this comment:

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

– Let’s just hope that whoever actually “fixes” this has a better understanding of asymptotic runtime than the writer of this comment, and realises that radix sort has a slightly more complex runtime description than simply O(N).

(Thanks to phsource for pointing out the error in the original answer.)

What is the fastest way to sort a large(ish) array of numbers in JavaScript

There are sort implementations that consistently beat the stock .sort (V8 at least), node-timsort being one of them. Example:

var SIZE = 1 << 20;
var a = [], b = [];
for(var i = 0; i < SIZE; i++) {    var r = (Math.random() * 10000) >>> 0;    a.push(r);    b.push(r);}
console.log(navigator.userAgent);
console.time("timsort");timsort.sort(a, (x, y) => x - y);console.timeEnd("timsort");
console.time("Array#sort");b.sort((x, y) => x - y);console.timeEnd("Array#sort");

<script src="https://rawgithub.com/mziccard/node-timsort/master/build/timsort.js"></script>

What is the stability of the Array.sort() method in different browsers?

As of ES2019, sort is required to be stable. In ECMAScript 1st edition through ES2018, it was allowed to be unstable.

Simple test case (ignore the heading, second set of numbers should be sequential if the engine's sort is stable). Note: This test case doesn't work for some versions of Chrome (technically, of V8) that switched sorting algorithms based on the size of the array, using a stable sort for small arrays but an unstable one for larger arrays. (Details.) See the end of the question for a modified version that makes the array large enough to trigger the behavior.

IE's sort has been stable as long as I've ever used it (so IE6). Checking again in IE8 and it appears to still be the case.

And although that Mozilla page you link to says Firefox's sort is stable, I definitely say this was not always the case prior to (and including) Firefox 2.0.

Some cursory results:

• IE6+: stable
• Firefox < 3: unstable
• Firefox >= 3: stable
• Chrome < 70: unstable
• Chrome >= 70: stable
• Opera < 10: unstable
• Opera >= 10: stable
• Safari 4: stable
• Edge: unstable for long arrays (>512 elements)

All tests on Windows.

See also: Fast stable sorting algorithm implementation in javascript

This test case (modified from here) will demonstrate the problem in V8 (for instance, Node v6, Chrome < v70) by ensuring the array has enough entries to pick the "more efficient" sort method; this is written with very old JavaScript engines in mind, so without modern features:

function Pair(_x, _y) {    this.x = _x;    this.y = _y;}function pairSort(a, b) {    return a.x - b.x;}var y = 0;var check = [];while (check.length < 100) {    check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y));}check.sort(pairSort);var min = {};var issues = 0;for (var i = 0; i < check.length; ++i) {    var entry = check[i];    var found = min[entry.x];    if (found) {        if (found.y > entry.y) {            console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y);            ++issues;        }    } else {        min[entry.x] = {x: entry.x, y: entry.y, i: i};    }}if (!issues) {    console.log("Sort appears to be stable");}

Why is the Array.sort() method in my Javascript program unstable?

Because JS' sorting is typically unstable. From §22.1.3.24 of the spec:

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order).

Your teams are created with identical properties except their name, so the line actually performing the sort is:

return teams.indexOf(a)-teams.indexOf(b);

Because you're calling indexOf, it searches for the item (and its index) each repetition of the sort. Sorting mutates the array (from MDN: it "sorts the elements of an array in place and returns the array").

You are searching for the item within the same array you are sorting, so the index may change on each iteration. Done correctly (relatively speaking), you could produce a never-ending sort with that.

For example:

const data = [1, 3, 2, 4];let reps = 0;
data.sort((a, b) => {  console.log(data);    const ia = data.indexOf(a), ib = data.indexOf(b);  if (ia === ib || reps > 50) {    return 0;  } else if (ia < ib) {    return 1;  } else if (ib < ia) {    return -1;  }    });

Sort in javascript - ignore sort when same value

What you're referring is called stability and refers to a sort algorithms capacity to maintain ordering among items that are considered equal. Not all algorithms can make that guarantee, and unfortunately the algorithm that you're using clearly doesn't.

I recommend you take a look at this article regarding sorting algorithms for a complete list.

Why Javascript implementation of Bubble sort much faster than others sorting algorithms?

That's because bubble sort is faster when you are sorting an array that is already sorted.

As you are sorting the same array over and over, it will be sorted in the first iteration in the first test, after that you are sorting an array that is already sorted.

To test the actual performance of sorting an array that is not already sorted, you have to create a new array for each sort iteration.

How can i write this algorithm so that it works stable

I see this as coming in two phases: a pre-processing phase in which you find all duplicated elements with their identifiers; a post-processing phase where you simply overwrite the found elements into their original order.

You didn't specify how you can differentiate elements that sort as the same value; I'll call that the id. In this first pass, construct a table with one row per value. Iterate through the array; store the id of each element (or the entire element) in the matching table row in the table. If there's already an element there, extend that row and store the current element.

At this point, if you wish, you can eliminate any row of the table with fewer than 2 elements.

For the post-procesing, iterate through the sorted array. If the value you find is in the table, then don't trust the order returned from Mystery-Sort. Instead, simply overwrite the next elements with the ones from that row of the table. This restores their original order.

When you reach the end of the sorted list, you're done.

---

Related Topics