Merge sort is a sorting technique based on a divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.
Merge sort first divides the array into equal halves and then combines them in a sorted manner.
In Merge Sort, the given unsorted array with n elements is divided into n subarrays, each having one element because a single element is always sorted in itself. Then, it repeatedly merges these subarrays, to produce newly sorted subarrays, and in the end, one complete sorted array is produced.
The concept of Divide and Conquer involves three steps:
1. Divide the problem into multiple small problems.
2. Conquer the subproblems by solving them. The idea is to break down the problem into atomic subproblems, where they are actually solved.
3. Combine the solutions of the subproblems to find the solution to the actual problem.
How merge Sort work
Following is the unsorted array
14
|
33
|
27
|
10
|
35
|
19
|
42
|
44
|
We know that merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved. We see here that an array of 8 items is divided into two arrays of size 4.
14
|
33
|
27
|
10
|
35
|
19
|
42
|
44
|
This does not change the sequence of appearance of items in the original. Now we divide these two arrays into halves.
14
|
33
|
27
|
10
|
35
|
19
|
42
|
44
|
We further divide these arrays and we achieve an atomic value which can no more be divided.
14
|
33
|
27
|
10
|
35
|
19
|
42
|
44
|
Now, we combine them in precisely the same manner as they were broken down. Please note the color codes given to these lists.
We first compare the element for each list and then combine them into another list in a sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the target list of 2 values we put 10 first, followed by 27. We change the order of 19 and 35 whereas 42 and 44 are placed sequentially.
14
|
33
|
10
|
27
|
19
|
35
|
42
|
44
|
In the next iteration of the combining phase, we compare lists of two data values and merge them into a list of found data values placing all in a sorted order.
10
|
14
|
27
|
33
|
19
|
35
|
42
|
44
|
After the final merging, the list should look like this –
10
|
14
|
19
|
27
|
33
|
35
|
42
|
44
|
C# program for merge sort
using System;
using System.Collections.Generic;
using System.Text;
namespace prog
{
class Program
{
static public void mergemethod(int[] numbers, int left, int mid, int right)
{
int[] temp = new int[25];
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i = 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
static public void Sorting(int[] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
Sorting(numbers, left, mid);
Sorting(numbers, (mid + 1), right);
mergemethod(numbers, left, (mid + 1), right);
}
}
static void Main(string[] args)
{
int[] numbers = { 14, 33,27, 10, 35, 19, 42, 44 };
int len = 8;
Console.WriteLine("MergeSort element :");
Sorting(numbers, 0, len - 1);
for (int i = 0; i < len; i++)
Console.WriteLine(numbers[i]);
Console.Read();
}
}
}
|
Complexity Analysis of Merge Sort
Merge Sort is quite fast and has a time complexity of O(n*log n). It is also a stable sort, which means the "equal" elements are ordered in the same order in the sorted list.
In this section, we will understand why the running time for merge sort is O(n*log n).
As we have already learned in Binary Search that whenever we divide a number into half in every step, it can be represented using a logarithmic function, which is log n and the number of steps can be represented by log n + 1(at most)
Also, we perform a single step operation to find out the middle of any subarray, i.e. O(1).
And to merge the subarrays, made by dividing the original array of n elements, a running time of O(n) will be required.
Hence the total time for mergeSort function will become n(log n + 1), which gives us a time complexity of O(n*log n).
Worst Case Time Complexity [ Big-O ]: O(n*log n)
Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: O(n*log n)
Space Complexity: O(n)
- The time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves.
- It requires an equal amount of additional space as the unsorted array. Hence it's not at all recommended for searching large unsorted arrays.
- It is the best Sorting technique used for sorting Linked Lists.
EmoticonEmoticon