Sorting Algorithms with Javascript (Part 1)

I've been learning a lot about data structures and algorithms lately and I've noticed in my reading that there aren't a lot of examples showing implementations of algorithms in Javascript. You'll mostly find examples in Java, Python, C, C++ etc. Maybe there's a reason for preferring these languages over Javascript? I'm not sure.

In this first part, I'm going to show Javascript implementations of three sorting algorithms:

• Merge sort
• Insertion sort
• Bubble sort

This is not intended to be an in-depth explanation on the ins and outs of how the algorithms work and their performance. If you'd rather read about that, here's a nice resource I found: Sorting Algorithms

To keep things simple, I'll be sorting a simple list list having only 5 elements [4, 2, 3, 1, 5].

Merge Sort

Merge sort uses a divide-and-conquer approach to sort elements in an array. Basically, what this means is that instead of dealing with the array as a whole, it continually splits it in half until both halves are sorted, then the halves are merged into one solved list.

Visual

Code

function mergeSort(list) {
  const len = list.length
  // an array of length == 1 is technically a sorted list
  if (len == 1) {
    return list
  }

  // get mid item
  const middleIndex = Math.ceil(len / 2)

  // split current list into two: left and right list
  let leftList = list.slice(0, middleIndex)
  let rightList = list.slice(middleIndex, len)

  leftList = mergeSort(leftList)
  rightList = mergeSort(rightList)

  return merge(leftList, rightList)
}

// Solve the sub-problems and merge them together
function merge(leftList, rightList) {
  const sorted = []
  while (leftList.length > 0 && rightList.length > 0) {
    const leftItem = leftList[0]
    const rightItem = rightList[0]
    if (leftItem > rightItem) {
      sorted.push(rightItem)
      rightList.shift()
    } else {
      sorted.push(leftItem);
      leftList.shift()
    }
  }

  // if left list has items, add what is left to the results
  while (leftList.length !== 0) {
    sorted.push(leftList[0])
    leftList.shift()
  }

  // if right list has items, add what is left to the results
  while (rightList.length !== 0) {
    sorted.push(rightList[0])
    rightList.shift()
  }

  // merge the left and right list
  return sorted
}

const list = [4, 2, 3, 1, 5]

const sorted = mergeSort(list)

console.log(sorted)

Insertion Sort

Insertion sort builds the final sorted list one element at a time. It does this by taking one element, comparing it to the rest of elements in the list, finding its right position, and then placing it there.

This is known as comparison-based sorting.

Visual

Code

function insertionSort(list) {
  const len = list.length
  for (let i = 1; i < len; i++) 
  {
    if (list[i] < list[0]) 
    {
      // move current element to the first position
      list.unshift(list.splice(i,1)[0])
    } 
    else if (list[i] > list[i-1]) 
    {
      // maintain element position
      continue
    } 
    else {
      // find where element should go
      for (let j = 1; j < i; j++) {
        if (list[i] >= list[j-1] && list[i] <= list[j]) 
        {
          // move element
          list.splice(j, 0, list.splice(i,1)[0])
        }
      }
    }
  }
  return list
}

const list = [4, 2, 3, 1, 5]

const sorted = insertionSort(list)

console.log(sorted)

Bubble Sort

Another example of a comparison-based sorting algorithm, Bubble sort compares each pair of elements in a list and swaps them if they are out of order until the list is sorted.

Visual

Code

function bubbleSort(list)
{
    let swapped
    let n = list.length-1
    do {
        swapped = false
        for (let i=0; i < n; i++)
        {
            // compare pairs of elements
            // if left element > right element, swap
            if (list[i] > list[i+1])
            {
               const temp = list[i]
               list[i] = list[i+1]
               list[i+1] = temp
               swapped = true
            }
        }
    } 
  // continue swapping until sorted
  while (swapped) 

  return list
}

const list = [4, 2, 3, 1, 5]

const sorted = bubbleSort(list)

console.log(sorted)

Thats it! 😊 And, incase you're wondering, I used this site to make the visuals.

In the next part, I'll be going through:

• Quick sort
• Heap sort
• Counting sort

Comments

[João Quintanilha]

Hello there! First let me thank you for the article, it helped me a lot. As I was developing an insertion sort I came across your code and used it, although you have a litle mistake I ended up finding.

instead of:
if (list[i] > list[j-1] && list[i] < list[j])

you should have (= is missing on second validation):
if (list[i] > list[j-1] && list[i] =< list[j])

Otherwise, it wont sort. Once again, thank you!

[Kelvin Wangonya]

Hey there! I'm glad you found it helpful. Thanks for that 😄.

The code seems to work just fine with the test list provided though. Would you mind explaining why the = is necessary? Or maybe share the list you tested the code with so I can also try it.

Ps: The = should be on the other side of the < in your example though, like so: if (list[i] > list[j-1] && list[i] <= list[j]) 🙂

[Lynn Mugambi]

Hey Kinyanjui, thanks again for the post! Super helpful!

Just hoping on to this, I noticed an issue with the same line of code where if a list has two elements with the same value it won't sort it properly. i.e. [4, 2, 3, 2, 1, 5] gives [ 1, 2, 3, 4, 2, 5 ] as a result.

Adding an = sign to the first argument makes all the difference! if (list[i] >= list[j-1] && list[i] < list[j]). It now returns [ 1, 2, 2, 3, 4, 5 ] :)

[Kelvin Wangonya]

Thanks Lynn. I've edited the code to include your fix.

[Christian Baer]

Hey, nice overview. One thing though. Merge sort is also comparison based. To sort in the end, you always compare two elements.

[Kelvin Wangonya]

Nice catch! Thanks

[Adrian Vaucoret]

Hello guy ! Nice post !

What is the faster sort algorithm ? Is it depends of number of elements ?

[Kelvin Wangonya]

Thanks for reading!

In this case, Merge sort is the faster of the three with time complexity O(nlogn). Time complexity (the estimated time taken by running an algorithm) is measured by how many operations are executed so yes, the number of elements will matter, but not as much as the order of the elements:

• Worst-case time complexity (input elements in reversed order)
• Best-case time complexity (already sorted)
• Average-case time complexity (elements in random order)

[Aditya Sridhar]

Nice Article. Thanks for taking the time to write this :)

[Kelvin Wangonya]

Thanks for taking the time to read Aditya :)