what I learned last week: merge sort algorithm

I know it's been several weeks since I last posted an entry but I'm happy to be back after successfully completing General Assembly's Java Immersive Program!

Prerequisite: Recursion

Lets get right to it. In this entry I'm going to go over Merge Sort which is a Divide and Conquer algorithm.

Remember, the divide and conquer technique can be divided into three parts:

1. Divide: This involves dividing the problem into smaller sub-problems.
2. Conquer: Solve sub-problems by calling recursively until solved.
3. Combine: Combine the sub-problems to get the final solution of the whole problem.

So, let's say you are asked to sort the unordered array below.

How would you achieve this and return this ordered array? One way, would be utilizing Merge Sort.

The first thing, we want to do is divide the unordered array into halves.

Next, I divide these two arrays into halves.

We further divide these arrays until we reach atomic value and the array can no longer be divided .

Now, I will combine them in a sorted manner.

Next, I continue combining the arrays in a sorted fashion.

The final merge will look like this.

You're probably asking yourself "how do I code the above algorithm?" First step, we need to write some pseudocode.

In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine reading.

Example Pseudocode

//array of elements
let arr = []

mergeSort(arr) {

//variable that stores number of elements in the array
n <-- array.length 

//cut the array into two halves
if(n < 2) {
    return n
  }

mid <-- n/2
left <-- array of size(mid)
right <-- array of size(n-mid)

for(i <- 0 to mid - 1) {
    left[i] <- arr[i]
  }

for(i <- mid to n - 1) {
    right[i - mid] <-- arr[i]
  }

//recursion
mergeSort(left)
mergeSort(right)
Merge(left, right, arr)
}

Justin Kim

Code Implementation in JavaScript

//helper method
const merge = (leftArr, rightArr) => {
    const output = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        const leftEl = leftArr[leftIndex];
        const rightEl = rightArr[rightIndex];

        if (leftEl < rightEl) {
            output.push(leftEl);
            leftIndex++;
        } else {
            output.push(rightEl);
            rightIndex++;
        }
    }
    return [...output, ...leftArr.slice(leftIndex), ...rightArr.slice(rightIndex)];
};

//console.log(merge([3, 6], [2, 4]));

//recursive function
const mergeSort = arr => {
    if (arr.length <= 1) {
        return arr;
    }

    const middleIndex = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, middleIndex);
    const rightArr = arr.slice(middleIndex);

    return merge(
        mergeSort(leftArr),
        mergeSort(rightArr)
    );
};


console.log(mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]));

Now if you run the program, you will see a newly sorted array

$ node app.js
[
    1,    1,   2,   2,   4,
    8,   32,  43,  43,  55,
   63,   92, 123, 123, 234,
  345, 5643
]

In conclusion, here is a group of folk dancers explaining Merge Sort. Yes, you read that right.

resources
https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.html
https://www.youtube.com/watch?v=TzeBrDU-JaY&t=69s
https://www.youtube.com/watch?v=x_Z9FcAPmbk