The Javascript sort is slow and stupid
Tags: programming, javascript, picture
Published: 2020-01-20 12:50:57

---
title: The Javascript sort is slow and stupid
published: true
date: 2020-01-18 21:41:50 UTC
tags: programming,javascript,picture
canonical_url: https://siderite.dev/blog/javascript-sort-slow-and-stupid/
---

Original post at [https://siderite.dev/blog/javascript-sort-slow-and-stupid](https://siderite.dev/blog/javascript-sort-slow-and-stupid)

![Sorting letter blocks](https://siderite.dev/Posts/files/Sorting_637149807996331781.png)  I was looking into the concept of [partial sorting](https://en.wikipedia.org/wiki/Partial_sorting "partial sorting is returning a list of the k smallest (or k largest) elements in order."), something that would help in a scenario where you want the **k** smaller or bigger items from an array of **n** items and **k** is significantly smaller than **n**. Since I am tinkering with [LInQer](https://siderite.dev/blog/linq-in-javascript-linqer/ "So many cool changes to this library now!"), my implementation for LINQ methods in Javascript, I wanted to tackle the _OrderBy(...).Take(k)_ situation. Anyway, doing that I found out some interesting things.

  First, the default Javascript array .sort function has different implementations depending on browser and by that I mean different sort algorithms. Chrome uses [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort "a simple sorting algorithm that builds the final sorted array (or list) one item at a time.") and Firefox uses [merge sort](https://en.wikipedia.org/wiki/Merge_sort "an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output."). None of them is [Quicksort](https://en.wikipedia.org/wiki/Quicksort "an efficient sorting algorithm, serving as a systematic method for placing the elements of a random access file or an array in order."), the one that would function best when the number of items is large. 

  ~~I've implemented a custom function to do Quicksort and after about 30000 items it becomes faster than the default one.  For a million items the default sort was almost three times slower than the Quicksort implementation. To be fair, I only tested this on Chrome. I have suspicions that the merge sort implementation might be better~~.

  I was reporting in a previous version of this post that QuickSort, implemented in Javascript, was faster than the default .sort function, but it seems this was only an artifact of the unit tests I was using. Afterwards, I've found an optimized version of quicksort and it performed three times faster on ten million integers. **I therefore conclude that the default sort implementation leaves a lot to be desired.**

  Second, the .sort function is by default alphanumeric. Try it: _[1,2,10].sort()_ will return _[1,10,2]_. In order to do it numerically you need to hack away at it with _[1,2,10].sort((i1,i2)=\>i1-i2)_. In order to sort the array based on the type of item, you need to do something like: _[1,2,10].sort((i1,i2)=\>i1\>i2?1:(i1\<i2?-1:0))_.

  And coming back to the partial sorting, you can't do that with the default implementation, but you can with Quicksort. Simply do not sort any partition that is above and below the indexes you need to get the items from. The increases in time are amazing!

  There is a difference between the browser implemented sort algorithms and QuickSort: they are [stable](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability "Stable sort algorithms sort repeated elements in the same order that they appear in the input."). QuickSort does not guarantee the order of items with equal sort keys. Here is an example: _[1,3,2,4,5,0].sort(i=\>i%2)_ results in _[2,4,0,1,3,5]_ (first even numbers, then odd, but in the same order as the original array). The QuickSort order depends on the choice of the pivot in the partition function, but assuming a clean down the middle index, the result is _[4,2,0,5,1,3]_. Note that in both cases the requirement has been met and the even numbers come first.