COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Merge Sort Algorithm in Data Structure II - Overview

$$/$$

In this video, Aishwarya shall complete the pseudocode for merge algorithm of Merge Sort. Let's see how the complete pseudocode for merge function looks like.

$$/$$

Video Transcript

 

Now, if you think that writing this while loop was sufficient for the merging process, then think about it carefully again. As you remember, in the example that we took, in the end we were left with only one element, that is, we were left with one element in array L, that is eight. Now, since this while loop is purely based on comparison, that is, these two if else conditions strictly only use comparisons to put elements into the A array, will I be able to use this while loop for inputting the last element in the L array? Well, no, because since there is no element left in R to compare, what will I compare my L element to? So, to ensure those cases in which one of my arrays gets exhausted and I am left with only elements in one array, I need to write some while loops for those conditions as well. That is, suppose my R array gets exhausted and I am left with a couple of elements in my L array. Then I need to sequentially write those elements in my A array. So that is what I'm doing here in this while loop. That is, this while loop will execute when my R array has become empty. What I need to do, I need to insert all the remaining elements in L array into A. So while my iterator L is less than the length of L, what I do is that I input the value of L of L in A of K, that is, I write L of L here in A of K and I move my L iterator one step ahead, that is L plus plus. And also I move my K iterator, which is pointing towards A array by one position. Now, similarly, this while loop I'm going to write for those conditions. Suppose my L array has become empty and I'm left with only some elements in element R. Now again, since there are no elements left to compare, I cannot use this while loop and I need to write a different while loop for inputting all my remaining elements into array. So this while loop says that while R is less than the length of R array, I'll write my value of R of R into A of K and I will increase my R iterator by one. And also I will increase my K iterator by one. So, if you look at this carefully again, you would know that at any given point of time, only one of these while loops will execute because only one of these while conditions would be true. So in the first while loop, what was happening? The first while loop was for those cases in which I have elements in both my L and R array. In that case, I was sequentially comparing each element in L and R and based on that, I was writing the smaller of those two values into A of K. Moreover, then I wrote my next while loop for those cases in which my R array has become empty and I am left with only elements in my L array. In that case, I was writing all those remaining elements in L array into A, that is, A of K is equal to L of L and incrementing my L and K pointers. Lastly, if I reach a situation when I am exhausted with elements in L, that is, my L has become empty and I am left with elements only in R. In that case, I was taking all the remaining elements in R and writing them to A of K and I was again incrementing my R and K pointer. So this is how this merge code is now fully complete. Now, here's a question for you. If you look at this code here and related to the example which we learned, what do you think? Which of these conditions here in this while loop was getting violated, because of which our program knew that it has to come out of this while loop? I'm talking about the last step here. When I was left with only one element in L and my R was exhausted. So which of these conditions here in the while loop was getting violated, which made the program to understand that it has to come out of this while loop? So think about it and write it in the question that follows. So in the example which we took, my R, iterator reached the end of the R array. That is, I was no longer left with any element to compare in my R array. It was because my small R, which was my iterator reached the length of R, that is, my small R became equal to N of R. So when my small R is equal to n of R, do you think this while condition will be true? Well, no, because this while condition is true only while R is less than NR, and since in our case, R became equal to NR, so this particular condition was violated. And because of it, the program came to know that it no longer can execute this while loop, and it must move ahead to either of these two while loops.

 

Video Recap

 

 The while loop used for merging arrays may not be sufficient for cases where one of the arrays has already been exhausted.

  • Additional while loops are needed to handle these cases.

  • A while loop is needed to insert remaining elements from array L into the merged array A when array R has become empty.

  • Another while loop is needed to insert remaining elements from array R into the merged array A when array L has become empty.

  • At any given point in time, only one of these while loops will execute.

  • The program knows to come out of the while loop when the R iterator reaches the end of the R array.

  • In the example provided, the small R iterator became equal to the length of R, violating the while condition and causing the program to exit the loop.

 

The 2 arrays which we were merging into one sorted array were themselves sorted. How do you think those 2 arrays were sorted? Let's move onto the next video to find an answer to this question.

$$/$$

In the next video, Rachit will sort the same deck of cards using Merge Sort. Let's see how he does that.

$$/$$

So, what you have learnt till now is following -

  1. How Merge Sort works.
  2. Pseudocode for Merge function

What is left to be learnt is the pseudocode for the portion of the algorithm we discussed in the video above i.e. where we break the array into arrays of one element each. Let's move on to the next video where we complete the pseudocode for Merge Sort algorithm.

$$/$$

In the above video at timestamp 1:59, where the instructor is explaining the for loop for populating arrays L and R, an equal to (=) sign is missing in both the for loops. For pseudocode to consider both lower and upper bound elements equal to is necessary. So the modified pseudocode is as follows.

MergeSort(A)
     n=length(A)
     if (n<2) return 
     mid=n/2
     L=A[0...mid-1]
     R=A[mid....n-1]
     for   0<= l <=mid-1
         L[l]=A[l]
     for  mid<= r <=n-1
         R[r-mid]=A[r]
     MergeSort(L) 
     MergeSort(R) 
     Merge(L,R,A)

 

Awesome! Now that you are comfortable with both the algorithm and its pseudocode, it's time to have a look at it's Java implementation as well. We do that in the next segment.