Array#sort implementations are not interoperable

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>

Oops, sorry everyone, looks like I had a serious copy-paste mishap with
gmail. :/

On Sat, Dec 1, 2012 at 3:10 PM, Jussi Kalliokoski <
jussi.kalliokoski at gmail.com> wrote:

> 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/44021616/attachment-0001.html>