4115724, 3:01 PM Morge Sor Tutorials & Notes | Algorithms | HackerEarh Signup and get ree access to 100+ Tutorials and practice Problems [Stow | £8 q Algorithms Topics: Merge Sort . Merge Sort Problems Tutorial Visualizer Merge sorts a divide-and-conquer algorithm based on the idea of breaking down a list into several sublists untl each sublist consists of 2 single element and merging those sublsts in manner that resus into 2 sorted lt. tea “+ Divide the unsorted lst into N’ sublists, each containing 1 element. “+ Toke acjacent pairs of two singleton sts and merge them to form a Ist of 2 elements, N will now corwert into N/2 lists of size 2. ‘+ Repeat the process tila single sorted list of obtained While comparing two sublists for merging, the frst element of both lists is taken into consideration. While sorting in ascending order, the clement that is of a lesser value becomes a new element of the sorted lit. This procedure is repeated untl both the smaller sublists are empty and the new combined sublst comprises al the elements of both the sublsts Lees consider the following image intps:wwwsnackerearth.comipracticelalgotmsisortingimerge-sorttutoral 454115724, 3:01 PM Morge Sor Tutorials & Notes | Algorithms | HackerEart Merge Sort 9|7|/s|3|}2]4 } mid = (0+5)/2=2 2)/2=1 y mid = (3+5)/2=4 o.- ~@ oOo}: © ie == A : = ntps:wwwnackerearth.comipractcelalgothmsisortingimerge-sorttutoral 2154115724, 3:01 PM Morge Sor Tutorials & Notes | Algorithms | HackerEarh ‘As one may understand from the image above, at each step a Ist of size M Is being divided into 2 sublists of size M/2, untl no further division ean be done. To understand better, consider a smaller array A containing the elements (9,7, 8) A the first step Wis lst of size 8 Is divided into 2 sublists the frst consisting of elements (9,7) and the second one being (8). Now, the fist lst consisting of elements (9,7) Is further divided into 2 sublists consisting af elements (9) and (7) respectively ‘Asn further breakdown ofthis lst can be done, as each sublstconslsts of a maximum of I element, we now start co merge these Ist. The 2 subilists forrned inthe last step are then merged together In sorted order using the procedure mentioned above leading to 2 new lst (7,9). Backerackng further, we then need to merge thelist consisting of element (8) too with this lst leading to the new sorted Ist (7, 8,9) ‘An implementation has been provided below void merge(int Af], dnt stant, dnt aia, Ant end) ¢ U/stores the starting position of both parts in temporary variables, int p = start ,q = nies; Ant Arr[end-startea] , K-23 for(int {= start 34 <= end sit) { Af(p > mid) //ehecks if First part comes to an end on not Arr{ kes J = AL ase] 5 else if (-q > end) —//checks if second part cones to an end or not Aer( ket J = AL pe Js else HFC AL > 1 < AL @ 1) //checks which part hos snoller element. aer{ ket J = AL pte 15 else Aer{ kee J = AL aes) y for (int p-@ j pe k ip 4) ( /* Wow the real array has elements (n sorted manner inctuding both ports.*/ AC startes ] = APeE p Ds Here, in merge function, we will merge two parts ofthe arrays where one part has starting and ending positions from start to mid respectively and another part has positions from mid#1 to the end, ‘beginning s made from the staring parts of both arrays. le. p and q, Then the respective elements of both the parts are compared and the one withthe smaller value will be store in the auxiliary array (Arr). If at some condition one part comes to end then all the elements lof another part of array are added in the auxilary aray in the same order they exis. Now consider the following 2 branched recursive function, void nerge sort (int A[ ] , int start , int end ) « 4#( start < end) Ant mid ~ (start + end) /25 U1 defines the current array in 2 parts merge_sort (A, start , mid ) 5 U1 sort the Ast port of array merge _sort (Ayeidel , end ) 5 U1 sort the 2nd part of array. 17 merge the both ports by comparing etements of both the parts. rmerge(Aystart , mid , end ); intps:twwnackerearth.comipractcelalgottmsisortingimerge-sorttutoral4115724, 3:01 PM Morge Sor Tutorials & Notes | Algorithms | HackerEarh > Time Complexity: ‘The lst of size Wis divided into a max of loglV parts, and the merging of all sublists into singe ist takes O(N) time, the worst case run time of this algorithm is O(N Leg) Contoured by Anand singh Did you find this tutorial helpful? © Yes © No ‘TEST YOUR UNDERSTANDING MergeSort Given an array A on size N, you need to find the number of ordered pairs (i, 4) such that 4 < jand Ali] > Aly] Input: line contains one integer, W, size of array. Second tine contains N space separated integers denoting the elements ofthe array A. ‘output: Print the number of ordered pairs (i, ) such that { Alj. Constraints: 1sNs10° 1< Afi] < 10° saw npur %@ saws oureur we Enter your ode or Upload your code as le save Cigee 10.3) 28 1 include 2 3 Ant main(¢ 4 int nus; 5 seanf(°%2", nun); 11 Reading input fron STOIN 6 peint#("Input nunber Ss Xd.\n", nun); 11 soiting output to SToOUT 7) 8 hntps:wwwnackerearth.comipracticelalgotmsisortingimerge-sorttutoral4115724, 3:01 PM For sales enquiry support@hackerearth.com or support support@hackerearth.com ‘Test against custom input ¥ Morge Sor Tutorials & Notes | Algorithms | HackerEarh For Developers For Businesses Knowledge Hackathons Hackathons Practice Challenges Assessments, Interview Prep. Jobs FaceCode Codemonk Practice Learning and Development Engineering Blog Campus Ambassadors Compile &Test code | submit cove Company About us Careers Press Support Contact Privacy (© 2024 Hackertarth All igs reserved | Terms of Service | Privacy Policy intps:wwinackerearth.comipracticelalgottmsisortingimerge-sorttutorial