Understanding consistently wrong behavior with sort()

Question

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

1. I know sort() is supposed to be used only with numbers
2. I know that comparing strings with - is a bad idea
3. I already localized and fixed the original bug in my code, but...

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).

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?

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].

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:

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)