Data Science & Algorithms: Merge Sort

Welcome To Part 2 Of My Introduction To Data Science & Algorithms Blog! In today's post, we will go through the "Merge Sort" Algorithm. And just like last time, I'll give you a code example in Python and JavaScript.

So, how does Merge Sort work?
Well, Merge Sort is considered a divide and conquer algorithm( learn about divide and conquer here).
The way that it works is by diving the array into 2 equal( in terms of length) mini arrays, doing this again until each array is sorted then merges them.

To better understand this here is a photo from google:

Now that you understand the logic behing Merge Sort, let's look at code examples:

Here is Merge Sort in Python code:

def mergeSort(arr):
    if len(arr) > 1:
        n = len(arr)//2
        l = arr[:n] # get the left half of the array
        r = arr[n:] # get the right half of the array

        # Sort the two mini arrays
        mergeSort(l)
        mergeSort(r)

        i = j = k = 0

        # I can't really explain this I'm sorry
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                arr[k] = l[i]
                i += 1
            else:
                arr[k] = r[j]
                j += 1

            k += 1

        # insert the remaining elements in arr
        while i < len(l):
            arr[k] = l[i]
            i += 1
            k += 1

        while j < len(r):
            arr[k] = r[j]
            j += 1
            k += 1


arr = [-6, 5, 0, 69, 42, 1]

mergeSort(arr)

print(arr)

"""
Output:
[-6, 0, 1, 5, 42, 69]
"""

And here is the JavaScript example:

function merge(left, right) {
  let sortedArr = []; // the sorted elements will go here

  while (left.length && right.length) {
    // insert the smallest element to the sortedArr
    if (left[0] < right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }

  // use spread operator and create a new array, combining the three arrays
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  const half = arr.length / 2;

  // the base case is array length <=1
  if (arr.length <= 1) {
    return arr;
  }

  const left = arr.splice(0, half); // the first half of the array
  const right = arr;
  return merge(mergeSort(left), mergeSort(right));
}

var arr = [-6, 5, 0, 69, 42, 1];
arr = mergeSort(arr);
console.log(arr)

/*
Output:
[-6, 0, 1, 5, 42, 69]
*/

Code by sebhastian.com

That was all for today’s blog! Hope you enjoyed it😁 and don’t forget to ❤️!