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 I - Overview

$$/$$

Let's quickly hop on to the next video where you will learn how Merge Sort works.

$$/$$

Video Transcript

 

So in this session, we are going to take a look at two very interesting sorting algorithms. One of them is merge sort and the other is quicksort. So what is good about merge sort? So you have read in the previous session that the three sorting algorithms we looked at bubble sort, insertion sort and selection sort, had the worst case time complexity of order n square. Now, is there a sorting algorithm which can sort, in the worst case scenario, in order n login? Yes, there is. So merge sort is one very good sorting algorithm which helps us to sort a given array of elements in the worst case scenario in order n login. So let us take a look at the basic idea behind how merge sort works. So, suppose you're given an array of elements like these. So you can see that these elements are not ordered. Now, suppose I have to arrange them in the increasing order. So what I can do is that perhaps I can divide these array of elements into two segments of four elements each. Now, imagine if I could have some way of sorting these individual arrays of four elements each individually, and then perhaps I can combine them to form a single sorted array of elements. So what I'm talking about is that suppose I have a way to sort this particular smaller array of four elements. So on sorting them, I would get something like this.

 

One would be here. So this is the sorted version of this. Similarly for this array, my sorted array would look like this. Now, suppose you are given these two segments of individually sorted elements. Now, can you think of some way as to how you can merge the elements in these two different group of elements into one single combined list, such that that combined list is sorted in itself? So think about it, how you can merge these two segments into one, such that all the elements are arranged in increasing order. So think about it and answer in the question that follows. 

 

Now that you are being introduced to the idea of how Merge Sort works, let's look at the video below to see how to merge those 2 sorted arrays into one single sorted array.

 

Video Recap

 

  • This session covers two sorting algorithms: Merge Sort and Quick Sort

  • Merge Sort has a worst-case time complexity of

  • The basic idea of Merge Sort is to divide an array into smaller segments and then merge them in sorted order

  • This is achieved by sorting each segment individually and then merging them together

  • The merged list is sorted in increasing order

  • Merge Sort is an efficient sorting algorithm for large data sets

  • It is possible to achieve worst-case time complexity of with Merge Sort

$$/$$

Awesome! Now you know how merge sort utilises ‘divide and conquer’ to sort an array. We keep dividing the array into two halves until we reach the single elements. Once we reach this stage, we start to merge them back in the required order. Let’s move on to the next video where we discuss the pseudocode for this merge function where we merge 2 sorted arrays into 1 single sorted array.