Project 6

Project 6

Published on 24 October 2020
  • Facebook
  • Twitter
  • Linkedin
sk
srujash kshirsagar
srujash's Personal Gallery
Transcript
00:00
All About Merge sort
00:01
00:05
00:06
One of the most popular sorting algorithms you'll bump into is mergesort. It was designed in the 1940's when dinosaurs roamed the jungles:
00:07
Type hereEver since then, mergesort (and variants of it!) can be seen everywhere - ranging from sort implementations in the Perl, Python, and Java languages to sorting data in tape drives. Ok, maybe the tape drives bit isn't relevant today, but mergesort comes up in a lot of places due to its efficiency. In this article, we are going to take a detailed look at how mergesort does its thing and wrap it up with a simple JavaScript implementation that brings it to life.
00:10
Type hereHow Mergesort Works
00:16
One quick aside. I should mention that mergesort is a divide and conquer algorithm...and it is quite shameless about that. All that it means is that mergesort performs its magic on numbers by dividing them into smaller and smaller sections first. Right now, we have nine numbers that we threw at mergesort. The first thing mergesort does is break that up into two halves:
00:21
00:21
Your original input is now divided into two sections. Next, we continue the dividing by breaking our two sections into four sections:
00:26
We are going to keep dividing these sections until you get to the point where you are left with just one number in each section and can't divide any further:
00:31
At this point, we have a bunch of individual values that look identical to what we started off with. That's not the goal of what we started out to do, but this is an important part of how mergesort functions. At this stage, we are done dividing. What we are going to see next is a whole lot of merging and sorting...aka the conquering part. Let's start with the first two sections:
00:41
We now repeat this for the next two sections made up of the numbers 4 and 1:
00:46
Just like before, we combine the two sections into one section. The sorting part is more clear this time around because the original arrangement wasn't already sorted. We start with a 4 and 1, and the merged arrangement is 1 and 4. Pretty simple so far, right? Now, we will keep repeating this merge and sort operation on each pair of sections until we run out of sections:
00:51
If you have a number that is the odd one and can't be a part of a merge and sort...like our number 10 here, that's OK. Stop making fun of it. We will just carry it along for the next round of merging and sorting and hope its luck improves! Earlier, we were merging pairs of sections that were made up of one number. That was easy. This time around, we are going to continue merging pairs of sections, but each section will contain two numbers. Take a look:
00:56
Instead of the merged section containing two numbers, it now contains four numbers...all in perfectly sorted bliss. We repeat this process for the remaining sections as well:
01:01
The number 10 is still not quite in the right position to be sorted and merged, so we'll drag it along for the next round:
01:06
By now, you should start to see a pattern emerge. We are nearing the home stretch here, so let's continue merging and sorting with the next row:
01:11
This almost looks fully sorted! We just have one one more round to go, and to those of you deeply worried about the number 10...it makes the cut this time around:
01:16
Wohooo! You now have a sorted list of numbers. There are no more sections to merge and sort, so you are done. As a quick recap (and to reminisce about all the good times we had), take a look at the full list of steps we performed to sort our initial collection of numbers:
01:21
The hard part is getting a good handle at how mergesort actually works. If everything in the previous section made sense to you, you are in great shape for the boring (yet important) details that you will need to know in addition. Ignoring all of the diagrams and fancy explanations, mergesort simply does two things:
01:21
Mergesort: The Boring Stuff
01:26
Divides (and divides, and divides, and....) its input into subsections until there is only one element left in each section. Merges (and sorts) all of its subsections back into one big section that is now sorted. It does all of this in n log n time, and the following tree representation highlights why that is the case:
01:36
To put in plain English, that is pretty fast and efficient for a sorting algorithm. The depth of your typical mergesort implementation is log n, and the number of operations at each level is n. When it comes to how much space it takes, things get a little less rosy. Common mergesort implementations take up 2n space in worst case scenarios - which is not terrible, but it is something to keep in mind if you are dealing with sorting within a fixed region of limited memory. The last detail is that mergesort is a stable sort. This means that the relative order of items is maintained between the original input and the sorted input. That's a good thing if you care about things like this.
01:41
Looking at the Code Now that you've learned how mergesort works and covered some boring details about its complexity, it is time to look at how all of that translates into JavaScript. Below is what my version of the JavaScript implementation looks like:
01:41
function mergeSort(input) { // just a single lonely item if (input.length < 2) { return input; } // divide var mid = Math.ceil(input.length / 2); var left = mergeSort(input.slice(0, mid)); var right = mergeSort(input.slice(mid))
01:46
// recursively sort and merge return merge(left, right); } function merge(left, right) { var result = []; // order the sublist as part of merging while (left.length > 0 && right.length > 0) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } }
01:51
// add the remaining items to the result while (left.length > 0) { result.push(left.shift()); } while (right.length > 0) { result.push(right.shift()); } // the sorted sublist return result; }