Merge Sort: Divide and Conquer Algorithm Explained
The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
- Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
- Conquer: Sort the two subsequences recursively using merge sort.
- Combine: Merge the two sorted subsequences to produce the sorted answer.
The recursion “bottoms out” when the sequence to be sorted has length 1, in which case there is no work to be done, since every sequence of length 1 is already in sorted order.
Key operation of the merge sort algorithm is the merging of two sorted sequences in the “combine” step. We merge by calling an auxiliary procedure MERGE (A, p, q, r), where A is an array and p, q, and r are indices into the array such that p ≤ q < r. The procedure assumes that the sub arrays A [p…q] and A [q + 1…r] are in sorted order. It merges them to form a single sorted sub array that replaces the current sub array A [p…r].
Merge_sort (A, p, q)
{
if (p = = q)
return A[p];
else
{
//only one element
mid = (p + q)/2;
Merge_sort (A, p, mid);
Merge_sort (A, mid + 1, q);
Merge algorithm (A, p, mid, q);
return A;
}
}
We are assuming merge algorithm takes θ(n) time. Later, will prove that our assumptions are correct.
Recurrence Relation for Time Complexity
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
