JavaScript: Array.prototype.sort

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: unless all elements in array are strings of ASCII Characters, you should always add a sort function.

// 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 makes 40 before 9, because elements are compared as string.

// warning: array sort problem. 40 comes before 9

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

Default Order Function

If order function is not given, each element is forced to a string by toString method, then each “character” compare by their Code Unit . (WARNING: not character's Codepoint)

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

*/

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]`);

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.

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

Note: the custom order function must be consistent, else the result of sort is implementation dependent.

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:

• typeof f(x,y) === "number" and is not NaN
• f(x,y) always returns the same value.
• Calling f(x,y) does not modify the array or any object of array's Prototype Chain.