Often times in programming you‘ve got an array that is out of order, and values are just thrown in there because you know they’re important. Well, now I’d like to display those array values in a specific order. How might we do that?
Everyone who has ever shopped online has seen a list of products in front of them. Everyone has also seen that “Filter” button at the top of the screen as well! That filter button is a way to sort out the list of products you see in front of you, whether it be excluding certain categories of items or organizing the items with the least expensive items at the top (my personal favorite). This is why sorting algorithms are an important aspect of programming!
Divide and Conquer
Divide and Conquer is a programming paradigm that Merge Sort and Quicksort algorithms use. It is an algorithm based on recursion, and it is broken down into 3 main steps:
- Divide the problem into subproblems that are simply smaller instances of the original problem.
- Conquer the subproblems by solving them recursively. If the problem is small enough, then that is the base problem.
- Combine the solutions to the subproblems to the solution for the original problem
Here’s what it looks like:
Let’s take a look at a sorting problem, and solve it using the Merge Sort algorithm.
Our problem is that we have an array of numbers that is out of order. Our job is to put these numbers in order from least to greatest. Here is the array:
[4, 8, 7, 2, 11, 1, 3]
Here’s how were going to do this:
- Split the given list of numbers into two halves (roughly equal halves)
- Continue dividing the subarrays in the same manner until you are left with only single element arrays
- Starting with the single element arrays, merge the subarrays so that each merged subarray is sorted
- Repeat step 3 until we end up with a single sorted array
We are first going to write our merge() function that takes two sorted subarrays and transforms them into one sorted array. Remember, both subarrays are already sorted, we are not just merging them together.
In the function above, we take two sorted subarrays (left, right) and merge them to get a single sorted array. First, we create an empty array (arr). We then pick the smaller of the smallest unpicked element in the left and right subarrays and push them into the empty array. We need to only check the first elements in left and right subarrays since they are both sorted.
While doing this, we delete the picked element from the subarray (using shift()). We continue until one of the subarrays becomes empty. After that, we push the leftover elements of the non-empty subarray into the main array.
As we now have the conquer aspect of our divide and conquer paradigm, the only part left to do is to keep splitting our arrays until we end up with arrays that only contain one element.
Here, we identify the midpoint and split the array into two subarrays using splice(). If there is an odd number of elements, the left one gets a smaller number of elements. We divide until we are left with single element arrays (array.length < 2). After that, we start combining the subarrays using our merge() that has already been defined.
Now that we’ve got our Merge Sort functions written out, lets see them solve our problem!
That’s awesome! We’ve sorted our array from least to greatest using our Merge Sort algorithm!
The beauty of this algorithm is not seen when testing it on a small array such as the example we used above. This algorithm really shines when using it on large arrays, cutting the time it takes for the function to run by a large amount.
I hope you now understand the importance of Merge Sort, as well as the Divide and Conquer paradigm. I hope to see you again in the future for more algorithm learning and practice. Happy coding!
Divide and conquer algorithms (article) | Khan Academy
If you're seeing this message, it means we're having trouble loading external resources on our website.