Array#sort implementations are not interoperable

Jussi Kalliokoski jussi.kalliokoski at gmail.com
Sat Dec 1 05:10:19 PST 2012


Hello everyone,

I was thinking about sorting algorithms yesterday and I realized that ES
implementations may have different sorting algorithms in use, and decided
to try it out. Now, if you sort strings or numbers, it doesn't matter, but
you may be sorting objects by a key and this is where things get nasty
(think non-deterministic vs deterministic). Here's an example:

function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))

function shuffle (arr, depth) {
  /* it's a silly way to shuffle, but at least it's deterministic. */
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))

In Firefox, you get:

["s", "m", "q", "l", "e", "b", "k", "i", "f", "g", "o", "j", "d", "t", "n",
"c", "a", "p", "h", "r", "u"]
["f", "h", "a", "e", "b", "g", "j", "d", "c", "l", "r", "q", "o", "k", "t",
"n", "p", "u", "i", "m", "s"]

In Chrome, you get:

["s", "m", "q", "l", "e", "b", "k", "i", "f", "g", "o", "j", "d", "t", "n",
"c", "a", "p", "h", "r", "u"]
["f", "h", "a", "g", "e", "b", "j", "d", "c", "l", "r", "o", "q", "k", "n",
"t", "p", "u", "i", "m", "s"]

Real world consequences of this may include:

 * A blog where posts are sorted by date ("YYYY/MM/DD"). Different browsers
will show the posts in different order if Array#sort is used to accomplish
this. Not a very severe consequence.
 * A spreadsheet application. If it has some order-dependent algorithm to
calculate values, different browsers can give different results for the
same research data.

Now I'm not sure what could be done to this, if anything even should be,
just thought I'd bring it up.

Cheers,
Jussi

function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique
}))function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique
}))function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique
}))function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))

function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique
}))function shuffle (arr, depth) {
  var tmp = []

  var pi = String(Math.PI).substr(2)
  var i = 0
  var p = 0

  while (arr.length) {
    i = (i + +pi[p]) % arr.length
    p = (p + 1) % pi.length
    tmp.push(arr[i])
    arr.splice(i, 1)
  }

  if (!depth) return tmp

  return shuffle(tmp, depth - 1)
}

var unique = 'abcdefghijklmnopqrstu'
var sorter = 'deggeaeasemiuololizor'

var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
  return {
    unique: unique[i],
    sorter: sorter.charCodeAt(i)
  }
})

var original = shuffle(arr, 3)
var sorted = original.slice().sort(function (a, b) {
  return a.sorter - b.sorter
})

console.log(original.map(function (item) { return item.unique }))
console.log(sorted.map(function (item) { return item.unique }))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20121201/2841699c/attachment-0001.html>


More information about the es-discuss mailing list