Understanding consistently wrong behavior with sort()

I have the following code:

let arr = ;

for (i = 14; i <= 31; i++)
let d = "2018-08-" + String(i);
arr.push(
date: d
);


arr.sort((a, b) => a.date - b.date);

console.log(arr);

sort()

-

There is something that fascinates me about this buggy code: the result.

Subtracting a string from another string gives NaN, so I'd expect the array to stay the same (14, 15, 16, 17... 31), or maybe to get completely flipped (31, 30, 29, 28... 14).

NaN

14, 15, 16, 17... 31

31, 30, 29, 28... 14

Instead, the actual (consistent) result is

I'm very curious about knowing why exactly sort() is outputting that sequence of strings. Why 31, 15 and 23 get moved, and why do they get moved to those particular positions?

sort()

31

15

23

var arr = ; for (var i = 14; i <= 31; i++) arr.push(i); arr.sort((a, b) => "fubar"); console.log(arr)

If comparefn is not undefined and is not a consistent comparison function for the elements of this array (see below), the behaviour of sort is implementation-defined.

comparefn

v

Type(v) is Number, and v is not NaN

comparefn

1 Answer
1

This behavior is probably easier to understand with a simpler array.

For example:

let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

arr.sort(() => NaN)

console.log(arr)

In chrome this returns an array order like: [0,11,2,3,4,5,1,7,8,9,10,6].

[0,11,2,3,4,5,1,7,8,9,10,6]

This is peculiar, but if you look at the implementation of sorting in the V8 code you will find a mix of quicksort and insertion sort. In fact if will recursively call quicksort until the arrays being recursed on have a length less than 10, then it will switch to insertions sort.

The way quick sort chooses the pivot explains the behavior you're seeing. Here's a snippet with the slightly truncated code from V8:

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

function comparefn(a,b)
return NaN

function InsertionSort(a, from, to)
for (var i = from + 1; i < to; i++)
var element = a[i];
for (var j = i - 1; j >= from; j--)
var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0)
a[j + 1] = tmp;
else
break;


a[j + 1] = element;

;

function QuickSort(a, from, to)
var third_index = 0;
while (true)
// Insertion sort is faster for short arrays.
if (to - from <= 10)
InsertionSort(a, from, to);
return;

third_index = from + ((to - from) >> 1);

// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0)
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
// v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0)
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
else
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0)
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;


// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;

// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++)
var element = a[i];
var order = comparefn(element, pivot);
if (order < 0)
a[i] = a[low_end];
a[low_end] = element;
low_end++;
else if (order > 0)
do
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0)
element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;



if (to - high_start < low_end - from)
QuickSort(a, high_start, to);
to = low_end;
else
QuickSort(a, from, low_end);
from = high_start;


;

// run it
QuickSort(arr, 0, arr.length)

console.log(arr)

If you look at this, especially the way the pivot is chosen and when it switches to insertion sort, you will see why the results are ordered the way they are.

When the compare function always returns NaN, all the ifs in the code are bypassed that look like this:

if

var c12 = comparefn(v1, v2);
if (c12 > 0) /* etc /*


Meaning the whole sort reduces to the smaller:

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

function comparefn(a,b)
//console.log(a, b)
return NaN


function QuickSort(a, from, to)
var third_index = 0;
while (true)
// Insertion sort is faster for short arrays.
if (to - from <= 10)
return;

third_index = from + ((to - from) >> 1);
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];

a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
partition: for (var i = low_end + 1; i < high_start; i++)
var element = a[i];

if (to - high_start < low_end - from)
QuickSort(a, high_start, to);
to = low_end;
else
QuickSort(a, from, low_end);
from = high_start;


;
QuickSort(arr, 0, arr.length)
console.log(arr)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.