{"id":6241,"date":"2025-09-11T16:40:25","date_gmt":"2025-09-11T11:10:25","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6241"},"modified":"2025-09-11T16:40:25","modified_gmt":"2025-09-11T11:10:25","slug":"merge-sort-divide-and-conquer-algorithm-explained","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/algorithms\/merge-sort-divide-and-conquer-algorithm-explained","title":{"rendered":"Merge Sort: Divide and Conquer Algorithm Explained"},"content":{"rendered":"<p>The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.<\/p>\n<ul>\n<li>Divide: Divide the n-element sequence to be sorted into two subsequences of n\/2 elements each.<\/li>\n<li>Conquer: Sort the two subsequences recursively using merge sort.<\/li>\n<li>Combine: Merge the two sorted subsequences to produce the sorted answer.<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">The recursion \u201cbottoms out\u201d 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.<\/p>\n<p style=\"text-align: justify;\">Key operation of the merge sort algorithm is the merging of two sorted sequences in the \u201ccombine\u201d 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 \u2264 q &lt; r. The procedure assumes that the sub arrays A [p&#8230;q] and A [q + 1&#8230;r] are in sorted order. It merges them to form a single sorted sub array that replaces the current sub array A [p&#8230;r].<\/p>\n<p>Merge_sort (A, p, q)<\/p>\n<p>{<br \/>\nif (p = = q)<br \/>\nreturn A[p];<br \/>\nelse<br \/>\n{<br \/>\n\/\/only one element<br \/>\nmid = (p + q)\/2;<br \/>\nMerge_sort (A, p, mid);<br \/>\nMerge_sort (A, mid + 1, q);<br \/>\nMerge algorithm (A, p, mid, q);<br \/>\nreturn A;<br \/>\n}<br \/>\n}<br \/>\nWe are assuming merge algorithm takes \u03b8(n) time. Later, will prove that our assumptions are correct.<\/p>\n<p><strong>Recurrence Relation for Time Complexity<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6242 size-full\" src=\"https:\/\/study.madeeasy.in\/wp-content\/uploads\/2025\/09\/Recurrence.jpg\" alt=\"Recurrence\" width=\"289\" height=\"238\" \/><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows. Divide: Divide the n-element sequence to<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"quote","meta":{"footnotes":""},"categories":[1831,3],"tags":[1839,1838,1837],"class_list":["post-6241","post","type-post","status-publish","format-quote","hentry","category-algorithms","category-cs-it","tag-combine","tag-conquer","tag-recurrence-relation-for-time-complexity","post_format-post-format-quote"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6241","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6241"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6241\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6241"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}