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 Code in Data Structure - Overview

$$/$$

In the previous segments, if you notice carefully, you’ll see that we did two different operations. First, we divided the sequence up to single elements. Second, we merged them back in the required order. In the next video, you’ll see how you can do this in Java.

 

You can download the Java file for Merge Sort code being used in the video below.

$$/$$

Video Transcript

 

Now let us take a look at a simple implementation of the merge sort. So for here, let us first define a merge function which will take in an input array, the starting index of that input array, the middle element, the mid index of that input array and the ending index. So now what I'll do is first I'll calculate the length of my left subarray. So what will be my length of the left subarray? It will be the mid element minus the start index plus one. Now I'll calculate the length of the right subarray. So what will be the length of the right subarray? It will be n minus mid, that is n minus m. Now I'll declare two new subarrays l and r, which will store my left and right subarrays. After declaring them, I'll simply populate these two arrays. That is, I starting from zero till the left length I'll populate li equal to array of start plus i. Moreover, for populating my right subarray, I'll start my iterated j from zero going till the length of my right subarray. And I'll say r of j is equal to array of m plus j plus one. Now here I'll declare two new variables int I equals to zero and j equals to zero. And another variable k, whose initial value will be start. Now, in the coming procedure, we are going to do the actual merging process. So here I am saying that while I is less than the length of the left subarray and j is less than the length of the right subarray, if my l of I is less than equal to r of j, then I copy the value of the lesser element. That is, I copy the value of l of I into array of k and increment the I pointer. If the opposite is true, that is, if l of I is greater than r of j, then this means that r of j is a smaller value. And so I copy it into my array of k and increment the j pointer. Now after this, if else is over, I anyway have to increment my k pointer. So this is what we are doing here. Now, as we discussed in the pseudocode, there might arise a situation when my right array has exhausted and I'm only left with elements in the left subarray. In that case, what I'll do is that while my I is less than the length of the left subarray, I'll copy all such li elements into array of k. Then I will increment my I and k pointer.

 

Similarly, as we discussed in the pseudocode, if there arises a situation such that my left subarray has been exhausted and I am only left with my right subarray, in that case, I would sequentially copy all of my RJ values into array of k and increment the j and the k pointer. Now, let us look at this particular sorting function. What this sorting function does is that it takes in an input array, the starting index of that input array and the ending index. Now I say that if start is less than end then first I calculate the mid index which will be equal to start plus end by two. Then I'll call the same sort function on the smaller subarray that is sort of array comma start comma the mid. Similarly, I'll call the sort function on the remaining right subarray. So that will be sort of array comma m plus one comma end. And finally I will call my merge function taking in input parameters as array start m and end. Note that this merge function is the same which we defined here. Now let us try to run this code and see if it works correctly. For that we have taken an input array like this. This is clearly unsorted at this stage. Now we'll run and check. So here you can see that this array is finally getting printed in its correct sorted order. So this is how merge sort works.

 

Video Recap

 

 Merge sort is a sorting algorithm that utilizes the concept of divide and conquer.

  • A merge function is defined which takes in an input array, the starting index of that input array, the middle element, the mid index of that input array, and the ending index.

  • The length of the left and right subarrays are calculated.

  • Two new subarrays, i and r, are declared and populated with the respective elements of the left and right subarrays.

  • A merging process is executed where the smaller of the two elements is copied into a new array and the respective pointer is incremented.

  • If one of the subarrays has been exhausted, then the remaining elements of the other subarray are copied into the new array.

  • A sorting function is defined that takes in an input array, the starting index, and the ending index.

  • The sorting function calculates the mid index and calls itself recursively on the smaller subarrays.

  • Finally, the merge function is called on the left and right subarrays to sort and merge them.

  • The code is tested and verified to work correctly.

Note that the above code discussed by the Aishwarya is just one version of merge sort code being used. Obviously, it can have other versions as well.  One of those can be found here. Please do visit this link. It will help you broaden your understanding of the algorithm. 

Now, it's time to analyse this algorithm. We do it in the next segment.