Introduction to Sorting and Sorting Algorithms - Part 2 11-19-2013, 03:28 PM
#1
Merge Sort
What is Merge Sort?It is a sorting algorithm which uses comparison operator (=<) to choose which items of the 2 should be placed first, In fact it uses a well known method of "Divide and Conquer" to perform it's task.
Since the term MergeSort has 2 parts:
1) Merge
2) Sort
So I'll be explaining each part first and then will explain as whole In this way you'll under this better.
Understanding Divide and Conquer
This is an algorithmic approach, to break down tasks into sub task and then split these sub tasks to smaller sub tasks and going further until the condition reaches that it becomes simple enough to perform the task, Divide and Conquer is said to increase the efficiency of an algorithm because it breaks down hefty task into simple ones.
In order to understand the working, consider an array containing 6 integer values,
Code:
array = [1,3,2,8,5,9]Take a look at this pseudo code for our Divide And Conquer,
Code:
int middle = lenght.array / 2
array left, right;
loop through array:
for items before mid:
put them in left
for items after mid:
put them in right
call divide on left array againFirst when this divide function is called, it first finds the middle point of the array using which it can DIVIDE the array into two parts i.e Left and Right
Since the length of the array is 6, 6 / 2 = 3. The index 3 is our middle point and the item at index 3 is 8.
Hence when divide executes, it will separate all the items after and before 8, So
Code:
-> [1,3,2,8,5,9]
-> [1,3,2,| 8 |,5,9]
|
Mid PointThen the divide code will move toward the loop, The first line in the loop is to put all the items before and including 8 in the left array, So
Code:
-> [1,3,2,8 <- ,5,9]
-> left = [1,2,3,8]It has inserted all the items in the array left, Now insert all the items after 8 into right,
Code:
-> [1,3,2,8 -> ,5,9]
-> right = [5,9]Now, we can see, the initial array has been split into 2 other smaller arrays. Divide and Conquer is a Recursive algorithm, The condition for divide and conquer is to split a problem to an extent that it becomes easy to manage it. For us converting the list into sub arrays of length 1 is the job of Divide and Conquer and this can only be achieved by calling it again and again unless it fulfills the condition (Recursion)
To convert the list into more simpler one's we need to call it again which we did at the end for the left array, So lets cal divide on left array
Code:
-> left = [1,2,3,8]It will find the middle point again which comes to be 2,
Code:
-> [1,2,| 3 |,8]
-> left = [1,2,3]
-> right = [8]Once more we call it on the left,
Code:
-> [1, | 2 |,3]
-> Left = [1,2]
-> Right = [3]And again,
Code:
-> [1,2]
-> Left = [1]
-> Right = [2]No need to call divide and conquer again as the list has been broken down enough that we can call on the next function to sort it out. You see at each recursive call to the divide and conquer function, The list gets split into smaller and smaller sub lists, This is what Divide and Conquer does!
When a list has one element we call it sorted (As it has no other elements to be matched or compared with), So when Divide and Conquer creates a list which has 2 items, it splits them into half and then calls a function known as merge on them which we will study next.
Understand Merging
Merging is a process where you get to join two items (In case of our algorithm), but before joining this merge process compares the two given list, Lets take an example of 2 list items,
Code:
Left = 5
Right = 2Now when merge is called onto left and right list, this function will first compare both of them, making the following conditions:
Code:
1) If left[item] < right[item]
Put left item first then right
2) If right[item] > left[item]
Put right item before left item
3) Put leftover items in the endSo,
Code:
left = [5]
right = [2]
--> [5] < [2] (False)
--> [5] > [2] (True)
result = [2] [5]Now at the end these two items get Merged into one list
Code:
[2,5]In simple words, this function simply compares the two items, pick smaller of them, sorts them and then merges them into one.
Merge Sort Steps of Working
Merge Sort uses the following list of steps to perform it's job:
1) Divide
Divide the given list into sub list until each list contains 1 element
2) Conquer
Sort 2 sub list using merge recursion
3) Combine
When the two sub list are sorted, Merge them to produce a sorted list
Lets learn how Divide and Conquer is used by Merge Sort to do it's sorting, We will take a 7 length array
Code:
array = [5,9,1,4,10,12,8]First we call our divide function,
Code:
-> [5,9,1,4,10,12,8]
-> [5,9,1,4] [10,12,8]
-> [5,9] [1,4] [10,12] [8]
-> [5] [9] [1] [4] [10] [12] [8]This was achieved by the recursive calls to our divide function
Now we will call merge function on each of the two items,
Code:
-> [5] [9] [1] [4] [10] [12] [8]
-> ([5] [9]) ([1] [4]) ([10] [12]) ([8])
| | | |
-> [5,9] [1,4] [10,12] [8]Each of the two items are first compared keeping the strict conditions of the merge that we discussed,
As 5 is less than 9, hence it's in sorted form and the merge function merges them into one list exactly, same goes for the others. You might be noticing that lonely 8 at the end, If you recall, I did state that list with length 1 are considered sorted, hence 8 will continue as it is to the next step.
The next step is to call merge on these newly made lists, now the 2 list will get compared again
Code:
-> ([5,9] [1,4]) ([10,12] [8])
| |
-> [1,4,5,9] [8,10,12]The same process happened here, the right and left list items are compared, and put into order Lets visualize:
Code:
([5,9] [1,4])Item 5 of left list is compared to 1 of the right, Since 5 > 1 hence the resulting list will be,
Code:
[1]Then 5 is compared with 4, Since 5 > 4,
Code:
[1,4]The leftover list is [5,9] so it gets merge at the end,
Code:
[1,4,5,9]Now these last two remaining lists are merged further,
Code:
-> [1,4,5,9] [8,10,12]
-> [1,4,5,8,9,10,12]And we have a Sorted list using Merge Sort
Here's the whole process,
Code:
-> [5,9,1,4,10,12,8]
|
-> [5,9,1,4] [10,12,8]
| |
-> [5,9] [1,4] [10,12] [8]
| | | |
-> [5] [9] [1] [4] [10] [12] [8]
| | | | | |
-> ([5] [9]) ([1] [4]) ([10] [12]) ([8])
| | | |
-> [5,9] [1,4] [10,12] [8]
| |
-> ([5,9] [1,4]) ([10,12] [8])
| |
-> [1,4,5,9] [8,10,12]
| |
-> ([1,4,5,9] [8,10,12])
|
-> [1,4,5,8,9,10,12]Image:
![[Image: Merge-sort-example-300px.gif]](http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)
![[Image: mergesortA.png]](http://interactivepython.org/courselib/static/pythonds/_images/mergesortA.png)
![[Image: mergesortB.png]](http://interactivepython.org/courselib/static/pythonds/_images/mergesortB.png)
So merge sort actually splits the list into simpler ones, sorts em and merges them together. In the process tree you can see that after the middle of the tree the inverse process begins i.e First the list is split, then again it's merged back into one.
Here's one of my Merge Sort Implementation In C++:
Code:
#include "stdafx.h"
#include "iostream"
#include "vector"
std::vector<int> merge_list(std::vector<int> left, std::vector<int> right) {
//This vector holds all the items in sorted form at the end
std::vector<int>result;
//These variables will be used to iterate through the items
int go_left = 0, go_right = 0;
//Compare the size of the respective vectors until none of the item is left to be sorted
while (go_left < left.size() && go_right < right.size()) {
//Then compare the first 2
if (left[go_left] <= right[go_right]) {
//The smaller item gets inserted into the result vector
result.push_back(left[go_left]);
//Increase by 1
go_left++;
}
else {
//This is the part where the smaller item from the right vector gets inserted
result.push_back(right[go_right]);
//Increase by 1
go_right++;
}
}
//Insert the rest of the items till the point where none remains to be sorted
while (go_left < left.size()) //For the left vector
{
result.push_back(left[go_left]); //Insert into result
go_left++;//Increase by 1
}
while (go_right < right.size())//For the right vector
{
result.push_back(right[go_right]); //Insert into result
go_right++;//Increase by 1
}
//This finally returns the resultant vector (It might be the sublist or completly sorted) :)
return result;
}
std::vector<int> merge_sort(std::vector<int> list) {
//If the size(Number of items) is 1, Consider the list sorted
if (list.size() <= 1) return list;
//Find the midddle item of the list
int mid = (list.size() / 2);
//Vector to add items before the middle part
std::vector<int>left;
//Vector to add items after the middle part
std::vector<int>right;
//Vector iterator to loop through the vector and find the middle part and copy the items before it
for (std::vector<int>::const_iterator it = list.begin(), end = list.end() - mid; it != end; ++it) left.push_back(*it);
//Vector iterator to loop through the vector and find the middle part and copy the items after it
for (std::vector<int>::const_iterator it = list.begin() + mid, end = list.end(); it != end; ++it) right.push_back(*it);
//Recursive call to further merge the lists
right = merge_sort(right);
left = merge_sort(left);
//Call the merge list function and return the sorted list
return merge_list(left, right);
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> x = { 5, 90, 10, 18, 100, 201, 1, 11 };
int middle = (x.size() / 2);
std::vector<int> sorted = merge_sort(x);
std::cout << "Your sorted List is: " << "\n";
for (std::vector<int>::const_iterator it = sorted.begin(), end = sorted.end(); it != end; ++it){
std::cout << " " << *it << "\n";
}
}Advantages of Merge Sort:
1) It's faster even in worst cases, its complexity is same in both cases. For n = 20, it's 4.6 times faster than bubble sort. Merge sort's time complexity is Theta(nlg n) and space is BigOh(n), Merge sort is a very good sorting algorithm for n (input size) is very large.
Disadvantages:
Slower than non-comparison based algorithms
More Advantages: http://www.site.uottawa.ca/~nat/Courses/...sld026.htm
This ends my tutorial on Merge Sort, I hope you didn't find it confusing. Reading it 2 to 3 times will get it right. If you need any help I'm always available to answer your query via PM or email. For any corrections PM me
References: http://interactivepython.org/courselib/s...mergesorta, Wikipedia
Credits: @Psycho_Coder for his suggestions
![[+]](https://sinister.li/images/modern/collapse_collapsed.png)
![[Image: OilyCostlyEwe.gif]](http://fat.gfycat.com/OilyCostlyEwe.gif)
