JS: Array.prototype.sort

By Xah Lee. Date: . Last updated: .
arrayX.sort()
  • Sort arrayX in-place, return reference to the array.
  • Elements are converted to string for comparison, each character's Code Unit is compared for order.
  • arrayX can be a Array-Like Object.

πŸ›‘ WARNING: by spec, sort is not necessarily stable. That is, elements that are considered equal in order may be moved from the order they were in the original array.

πŸ›‘ WARNING: If order function is not given, each element is automatically converted to a string by toString method, then each β€œcharacter” compared by their Code Unit . (not character's Codepoint)

πŸ’‘ TIP: unless all elements in array are strings of ASCII Characters, you should always add a sort function as argument. 

// array sort example
const aa = ["a1", "a70", "a8", "A2"];

// default sort. element compared as string
const bb = aa.sort();

console.log(JSON.stringify(bb) === `["A2","a1","a70","a8"]`);

// the array is modified
console.log(JSON.stringify(aa) === `["A2","a1","a70","a8"]`);
// warning: array sort problem. 40 comes before 9

const aa = [9, 40, 2];
console.log(JSON.stringify(aa.sort()) === `[2,40,9]`);
arrayX.sort(f)
f is a ordering function. The function should take 2 arguments x y, and return:
  • negative number if x β‰Ί y
  • 0 if x = y
  • positive number if x ≻ y.
// sort array as numbers

const aa = [9, 40, 2];

const bb = aa.sort((x, y) => {
  if (x < y) return -1;
  if (x > y) return 1;
  if (x == y) return 0;
});

console.log(JSON.stringify(bb) === `[2,9,40]`);

Example: Default Order Function

Here is example showing it sorts by code unit and not codepoint.

/*
example showing default comparison function for string, sorts by code unit and not codepoint.
*/

console.log(["fi", "πŸ˜†"].sort());

/*
prints
[ "πŸ˜†", "fi" ]

the ligature fi has codepoint 64257
the smiley πŸ˜† has codepoint 128518
if order by codepoint, fi should come first.

fi
name: LATIN SMALL LIGATURE FI
codepoint 64257, U+FB01
UTF16 encoding: FB01

πŸ˜†
name: SMILING FACE WITH OPEN MOUTH AND TIGHTLY-CLOSED EYES
codepoint 128518, U+1f606
UTF16 encoding: D83D DE06

*/

Example: Custom Order Function

Sorting array using custom order function:

// array sort using custom function

// custom ordering function
const ff = ((x, y) => {
  // x and y are strings. we remove first char. consider rest as number
  const nx = parseInt(x.slice(1));
  const ny = parseInt(y.slice(1));

  if (nx < ny) return -1;
  if (nx > ny) return 1;
  if (nx == ny) return 0;
});

// sort by comparing as numbers after first char

console.log(
  ["a1", "a70", "a8", "A2"].sort(ff),
);
// [ 'a1', 'A2', 'a8', 'a70' ]

Order Function Must be Consistent

πŸ›‘ WARNING: The custom order function must be consistent, else the result of sort is unpredictable.

Consistent means, for any x y z in the array:

  1. f(x,x) === 0
  2. if f(x,y) === 0 and f(y,z) === 0 then f(x,z) === 0
  3. if f(x,y) === -1 and f(y,z) === -1 then f(x,z) === -1
  4. if f(x,y) === 1 and f(y,z) === 1 then f(x,z) === 1

The above guarantee that the set is partitioned into classes by a equivalence relation, and the equivalence classes are total ordered.

also, the following are required due to how JavaScript the language works: