If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the merge sort algorithm in JavaScript and Python.
This article originally published at jarednielsen.com
How to Code the Merge Sort Algorithm
Programming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the problem
Make a plan
Execute the plan
Evaluate the plan
Understand the Problem
Why do we need another sorting algorithm? What's the problem with the Bubble, Insertion, and Selection sorting algorithms? Why is their performance so slow? They each use nested iteration. If our goal is to improve the performance of our sorting algorithm, it follows that we need to do less iteration. But how do we do that?
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria, but this time let's up the ante:
GIVEN an array of unsorted numbers
WHEN my algorithm sorts the numbers
THEN the performance is faster than quadratic time complexity
That’s our general outline. We know our input conditions (an unsorted array) and our output requirements (a sorted array), and our goal is to organize the elements in the array in ascending, or non-descending, order with an order better than O(n^2).
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
Decomposition
Pattern recognition
Abstraction
Algorithm
If we are writing a sorting algorithm, we need to start with something to sort. Let’s declare an array of ‘unsorted’ integers:
[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]
When we are decomposing a problem, we want to break it into the types of problems that need to be solved. We also want to break it into the smallest problems that can be solved.
What’s the smallest problem we can solve?
Two numbers. We can shift the first two off our array…
[10, 1]
… and swap them:
[1, 10]
What is actually happening when we swap values in an array?
We need to slice the values into their own arrays, then concatenate the two arrays in sequential order.
Using our smallest problem as an example, [10, 1], we would break it into the following:
[10], [1]
Then do some conditional checkeroos and concatenate the two arrays back into one:
[1] + [10] = [1, 10]
Where have we seen this or something like it before?
Divide and conquer!
As we recalled above, in divide and conquer algorithms, we choose a pivot, and continuously divide the problem in two until we find a solution.
If you recall, our pivot is the length of the array divided by two. So, for our smallest problem where the length of our array is 2, our pivot will be 1.
Let's start pseudocoding this:
IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
RETURN arr
SET pivot TO THE LENGTH OF arr DIVIDED BY 2
Once we set our pivot, we can divide the array in two.
IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
RETURN arr
SET pivot TO THE LENGTH OF arr DIVIDED BY 2
SET left TO THE ELEMENTS PRECEDING pivot
SET right TO THE ELEMENTS SUCCEEDING pivot
Now what?
Now we need to run those conditional checkerinos and merge the two arrays.
Where have we see this or something like it before?
Merging two arrays!
Because we are pragmatic programmers, we are simply going to "import" that algorithm into this one. We'll do that by wrapping the pseudocode in a "FUNCTION":
FUNCTION merge(left, right)
SET result TO AN EMPTY ARRAY
WHILE THERE ARE ELEMENTS IN left OR right
IF THERE ARE ELEMENTS IN BOTH ARRAYS
IF THE FIRST VALUE IN left IS LESS THAN THE FIRST VALUE IN right
SHIFT THE FIRST VALUE OUT OF left AND PUSH IT INTO result
ELSE
SHIFT THE FIRST VALUE OUT OF right AND PUSH IT INTO result
ELSE IF THERE ARE ONLY ELEMENTS IN left
SHIFT THE FIRST VALUE OUT OF left AND PUSH IT INTO result
ELSE
SHIFT THE FIRST VALUE OUT OF right AND PUSH IT INTO result
RETURN result
Now we can simply call our merge function in our merge sort algorithm.
IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
RETURN arr
SET pivot TO THE LENGTH OF arr DIVIDED BY 2
SET left TO THE ELEMENTS PRECEDING pivot
SET right TO THE ELEMENTS SUCCEEDING pivot
RETURN merge(left, right)
Will this work?
Yes, but only if our array contains two elements.
What happens if we double our problem?
[10, 1, 9, 2]
If we follow the logic or our algorithm, we'll divide the array in two:
left = [10, 1]
right = [9, 2]
We'll then call our merge function like so:
merge(left, right)
Within our merge function, we will see that the first value in right is less than the first value in left, so we'll push that to result:
[9]
Uh oh! We're already in trouble!
In the next iteration we'll see that the first (and only) value in right is 2, which is less than the first value in left, 10, so we'll push 2 to result:
[9, 2]
If we follow the logic, we'll end up with a "sorted" array that looks like this:
[9, 2, 10, 1]
Not sorted, but definitely swapped!
What's the solution?
Our merge sort algorithm was beautiful when we were only working with two values.
How do we continually break a problem down into smaller, yet simliar, problems?
Recursion!
We can make recursive calls to merge sort to continually divide our problem in half until we reach our base case, at which point we'll return. And conquer!
Let's update our pseudocode:
FUNCTION merge sort
IF THE LENGTH OF arr IS LESS THAN OR EQUAL TO 1
RETURN arr
SET pivot TO THE LENGTH OF arr DIVIDED BY 2
SET left TO THE ELEMENTS PRECEDING pivot
SET right TO THE ELEMENTS SUCCEEDING pivot
RETURN merge(merge sort(left), merge sort(right))
Execute the Plan
Now it’s simply a matter of translating our pseudocode into the syntax of our programming language.
How to Code the Merge Sort Algorithm in JavaScript
Let’s start with JavaScript…
const merge = (left, right) => {
let result = [];
while(left.length || right.length) {
if(left.length && right.length) {
if(left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
} else if(left.length) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result;
};
const mergeSort = (arr) =>{
if(arr.length <= 1) {
return arr;
}
const pivot = arr.length / 2 ;
const left = arr.slice(0, pivot);
const right = arr.slice(pivot, arr.length);
return merge(mergeSort(left), mergeSort(right));
};
How to Code the Merge Sort Algorithm in Python
Now let’s see it in Python…
def merge(left, right):
result = []
while (len(left) or len(right)):
if (len(left) and len(right)):
if (left[0] < right[0]):
result.append(left.pop(0))
else:
result.append(right.pop(0))
elif (len(left)):
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result
def merge_sort(list):
if (len(list) <= 1):
return list
pivot = len(list) // 2
left = list[0:pivot]
right = list[pivot:]
return merge(merge_sort(left),merge_sort(right))
Evaluate the Plan
Can we do better?
It depends!
This is a standard implementation of merge sort, but there are still more sort algorithms to learn.
We'll look at quick sort in the next tutorial.
What is the Big O Of Merge Sort Sequence?
The order of our mergeSort algorithm is O(n log n), or log linear. You can learn more in my article on the topic: Big O Log Linear Time Complexity.
A is for Algorithms
Give yourself an A. Grab your copy of A is for Algorithms
Top comments (0)