JS: Array.prototype.sort

By Xah Lee. Date: . Last updated: .
xArray.sort()
  • Sort xArray in-place, return reference to the array.
  • Elements are converted to string for comparison, each character's Code Unit is compared for order.
  • Works on JS: Sparse Array. empty slots are filled as undefined and moved to the end.
  • xArray can be a Array-Like Object. return a Array-Like Object.

By spec, sort is stable. (new in JS: ECMAScript 2019)

🛑 WARNING: each Code Unit is compared, 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"]`);
// array default sort, items are treated as string
// 40 comes before 9

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

Sort xArray in-place, return reference to the array.

  • f is a ordering function.
  • f 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];

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

console.log(JSON.stringify(aa) === "[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' ]

Example: Sparse Array

works on JS: Sparse Array

empty slots are considered as having values of undefined, and moved to the end.

// using delete operator results a sparse
const aa = [9, 8, 0, 9, 4, 3];
delete aa[0];
delete aa[1];
console.log(aa);
// [ <2 empty items>, 0, 9, 4, 3 ]

// sort array as numbers
aa.sort((x, y) => {
  if (x < y) return -1;
  if (x > y) return 1;
  if (x == y) return 0;
});

console.log(aa);
// [ 0, 3, 4, 9, <2 empty items> ]

Example: Array-Like Object

works on JS: Array-Like Object

// create a array-like object
let xx = { 0: "b", 1: "a", length: 4 };

// sort a array-like object
Reflect.apply(Array.prototype.sort, xx, []);

// return array-like object
console.log(xx);
// { "0": "a", "1": "b", length: 2 }

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:

JavaScript. Sort, Reverse