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 ManagementMBA 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

Comparison of Sorting Algorithms in Data Structure

$$/$$

You have gone through five sorting algorithms until now. So, you have a good grasp of the time complexity of each algorithm. In this segment, you will compare them all to see which algorithm to choose in different cases.

$$/$$

Video Transcript

 

Now let us take a look at some of the important properties associated with Quicksort and merge sort. So the first property is that of stability. Here we can see that merge sort is stable, whereas Quicksort in not. So what do we mean by stability? By stability we mean that suppose I have a collection of coordinates like this, where this coordinate indicates the X coordinate and this coordinate indicates the Y coordinate. Now, suppose I have to sort these collection of coordinates according to the X coordinate. So here you would see that these two elements here, both of them have X coordinate equal to one. Now, what do you think is going to come here first? Is it going to be one comma five, or is it going to be one comma four? So if I use a stable sorting algorithm, in that case, the individual order of these two elements relative to each other will not be destroyed. That is, if I use a stable sorting algorithm, it will preserve the order between one comma five and one comma four. That is, one comma five will come here, then one comma four and then the rest of the elements sorted according to their X coordinate. So this was an example of stable sorting algorithm, whereas if I would have chosen an unstable sorting algorithm, it might be possible that here the order of one comma five and one comma four would have been interchanged. That is, the array would look something like this and so on. So what exactly is the utility of an algorithm being stable? Well, you can read about it in more detail in the link provided in this segment. But for now, just remember the fact that a stable sorting algorithm does not destroy the relative order of elements which have equal key, whereas you cannot guarantee anything in case of an unstable sorting algorithm. Now, let us take a look at a second property which we call as a sorting algorithm being in place. Here you can see that merge sort is not in place, whereas Quicksort is. So what does in place mean? So in place essentially means that if an algorithm uses extra space which is comparable to the size of the data set, that is, if I have an array of size n, and if I'm using an extra space of the size of order n itself, then that particular sorting algorithm is said to be not in place. Whereas if I do not use any additional data structures, or if the extra data structures which I am using is very less compared to the size of my data set that is very less than order n, then that particular algorithm is said to be in place. As an example, you can see in Quicksort what we were doing is that we were overwriting all our new elements, over the already existing array of elements. So there I was not using any additional array. That means that Quicksort was in place whereas in merch sort in each step I was dividing my array into two different subarrays and writing them down into new arrays by declaring new data structures. So my overall extra space which I was using was where much comparable to the size of the input array that is the extra space which I was using in case of merge sort was of the order of N and hence I say that merge sort is not in place.

 

Video Recap

 

 Quicksort and merge sort are important sorting algorithms

  • Merge sort is stable, whereas Quicksort is not

  • Stability refers to the preservation of the order between elements with equal keys during sorting

  • A stable sorting algorithm ensures that the relative order of such elements is not destroyed, unlike an unstable sorting algorithm

  • The utility of a stable sorting algorithm is explained in detail in a linked resource

  • Merge sort is not in place, whereas Quicksort is

  • In-place sorting algorithms do not use extra space comparable to the size of the data set being sorted

  • Quicksort is in place as it overwrites new elements over the already existing array of elements

  • Merge sort, on the other hand, creates new subarrays and data structures, using extra space of the order of N

  • In summary, Quicksort and merge sort have different properties such as stability and in-place sorting capabilities.

 

Now you have seen the essential differences between Merge Sort and Quick Sort when it comes to these algorithms being in-place and stable, let us now hear what Ankit has to tell us about comparing all the sorting algorithms we have learnt so far.

$$/$$

Great! Now you know that Bubble sort, Selection sort, and Insertion sort have a time complexity of O() in average and worst cases. So, generally they are not used unless we are very sure that the dataset is very close to the best case (where insertion sort has an O(N) time complexity). Both Merge sort and Quick Sort has an O(N log N) time complexity. But Quicksort has O( ) in worst case. Also, Merge sort is a stable sort, which Quicksort is not. So, in case you need a stable sorting algorithm, the only sorting algorithm you can opt for is Merge sort. 

 

Additional Reading

Stable Sorting Algorithm