DEV Community

Cover image for Common Sorting Algorithms in JavaScript

Common Sorting Algorithms in JavaScript

Christina on August 07, 2020

In this article, I will cover some common sorting algorithms in computer science. Sorting algorithms are important to study because they can often ...
Collapse
 
functional_js profile image
Functional Javascript

Excellent work Christina.
You're an expert of sorts. ;)

I perf-tested all of them.
The quickSort throws even on quite small arrays due to the stackoverflow recursion

The fastest is the merge sort, in the 1-2 second range for an array of 1M numbers.

Collapse
 
christinamcmahon profile image
Christina

First of all, good one πŸ˜‚

Second, thanks for double checking and good to know about your findings! Did you test it in codepen by chance?

Collapse
 
functional_js profile image
Functional Javascript • Edited

I perf-tested these locally.

An example usage per func...

//@perftests
const aNums = genRandNums(1, 1e4, 1e6);
timeInLoop("mergeSort", 1, () => mergeSort(aNums));

genRandNums Source Code

gist.github.com/funfunction/f7adf6...

timeInLoop Source Code

gist.github.com/funfunction/91b587...

Thread Thread
 
christinamcmahon profile image
Christina

Oh this is awesome, thanks for sharing!

Collapse
 
edh_developer profile image
edh_developer

Heapsort would be a good one to cover.

A few reasons:

  • heapsort is a good example of a pretty fast in-place algorithm
  • heaps are just generally good things to be aware of
  • heaps are relevant to improving the performance of mergesort, when you're doing a k-way merge with a large set of data
Collapse
 
christinamcmahon profile image
Christina

Good points! I'm considering writing another post as sort of a second part to this one and would likely include heap sort, counting sort, and radix sort... Thanks for the input, definitely makes me even more excited to continue learning about sorting algorithms!

Collapse
 
realdolos profile image
Dolores Greatamsky

The merge step of MergeSort comes in handy when needing to merge any number of already sorted sequences into one sorted sequence. I recently used it to merge hundreds of "sorted string table"-style files into one larger file, where the result wouldn't have fit in main memory. Remembering about MergeSort really helped me there 😁

Collapse
 
christinamcmahon profile image
Christina

Wow, that's a really cool use of the merge process, good thinking!

Collapse
 
wulymammoth profile image
David • Edited

Wow! You just keep firing! Nice work! I honestly don’t know the implementation for the slower sorts off the top of my head. What typically come to mind are O(n log n) sorting algos like quicksort, mergesort, and heapsort. Heap-sort has a lot of utility particularly on non-fixed size inputs (streams).

One note: I noticed that your merge function for mergesort could be improved β€” by not allocating a new array each time. The canonical implementation passes in the original array and replaces the elements in the original input array utilizing a third pointer within merge β€” this third pointer moves forward after a replacement and only one of the two pointers pointing at the smaller element of the two arrays being merged moves forward in each iteration. This halves the memory footprint of the current implementation.

Collapse
 
andreweastwood profile image
Andrew Eastwood

It seems that we need i + 1 < right at the quickSort example.

Collapse
 
polarisiota profile image
Polarisiota

Excellent!