Sorting Algorithms 2 - Introduction
Welcome to the Session 3 of this module — ‘Divide and Conquer’. In the previous session, you learnt about the following topics:
Bubble Sort
Selection Sort
Insertion Sort
In this session
In this session, you will learn about more efficient sorting algorithms with time complexities better than O(N). We will discuss the following sorting algorithms in this session:
Merge Sort
Quicksort
Please note that the guidelines for graded questions remain the same as they were in the previous session.
People you will hear from in this session
Subject Matter Expert
Aishwarya Rai
Ex-Product Engineer, EdgeVerve
She worked as a software developer for Finacle at Edgeverve and helped in creating financial and e-banking software applications. She is currently working with Software Development content team at UpGrad.
Industry Expert
Technical Lead, ImpactRun
ImpactRun is a fitness philanthropy Android application where your every walk or run raises funds for a social cause you care about.
Presenter
Rachit Goyal
In the next few segments, you will learn about a sorting algorithm called Merge sort. Please note that just like using the ‘divide and conquer’ logic improved the efficiency of search algorithms, merge sort will further improve the level of efficiency of sorting algorithms much like the same way. In the upcoming video, Ankit Maheshwari gives a brief introduction on the same. Let's have a look.
Video Transcript
Tuesday, in case you forgot. Divide and Conquer improve the Runtime of Our Algorithms when we discuss search algorithms, its importance is not limited to search algorithms only rather, as you will see, it will immensely improve the efficiency of sorting algorithms and will break the shackles of order and square and will take us to the land of logarithmic efficiencies. In previous videos, we have encountered a number of sorting algorithms, including bubble sort, selection sort, and insertion sort. But in real life, however, none of these methods are actually used to sort arrays. Most computer languages have built in sorting functions for arrays that save us from the time and effort of implementing our own sorting algorithms. And in many of these languages, the sorting algorithm that is employed under the hood is Merge, sort, or Quicksort. The reason we are going to dig deeper into Merge, sort and Quicksort is that even though they are built into almost all the programming languages, but still we are going to dig deeper because by studying how they work, we can decide better which one to pick when in our real life practical scenarios.
Video Recap
Divide and Conquer improves runtime of algorithms, not limited to search algorithms only.
It immensely improves the efficiency of sorting algorithms and breaks the shackles of order and square.
Bubble sort, selection sort, and insertion sort are sorting algorithms encountered in previous segments, but not actually used in real life.
Most computer languages have built-in sorting functions for arrays, with Merge sort or Quicksort employed under the hood.
By studying how Merge sort and Quicksort work, we can better decide which one to pick in real-life practical scenarios.
Let's move onto the next segment where Aishwarya will teach you how Merge Sort works.