Video credits: MyCodeSchool

In this lesson, we are going to talk about sorting algorithms. Sorting as a concept is deeply embedded in a lot of things that we do. It's quite often that we like to arrange things or data in certain order.
Sometimes to improve the readability of that data, at others to be able to search or extract some information quickly out of that data.

For example, something as simple as, when we are playing a card game, even though the number of cards in our hand is really less, we like to keep our hand of cards sorted by rank or suit.

Similry, when we go to a travel site to book a hotel ,then the site gives us all of sorting the hotels by price from low to high or by star rating or by guest rating.

I may be on a budget and I may want to avail the cheapest option.
So, I would sort the hotels by price from low to high and now, the cheapest hotel will be at the top. And, I may still try to strike a balance between rating and price.

So, sorting is a really helpful feature here and there are so many places where we like to keep our data sorted.

Be it the language dictionary where we want to keep the words sorted so that searching a word in the dictionary is easy or something like a medal tally where we want to know to see team is at the top and which team is not performing so well!

Definition

If we want to define sorting formally, then sorting is arranging the elements in a list or collection in increasing or decreasing order of some property.
The list should be homogeneous, that is all the elements in the list should be of same type.

To study sorting, to study sorting algorithms, most of the times we use a list of integers, and typically we sort the list of integers in increasing order of value.

 A sorted list is the permutation of the original list, When we sort a list, we just rearrange the elements.

Sorted data is good, not just for presentation or manual retrieval of information, even when we are using computational power of machines, sorted data is really helpful.

If a list is stored in computer's memory as unsorted, then to search something in this list, we will have to run Linear Search.
In linear search, we start with the first element of the list and keep scanning the whole list, until we get the element that we are looking for, so, in the worst case when an element will not be there in the list, we will compare it with all the elements in the list, we will scan it with whole list.

So, if there are n elements in the list, we will make n comparisons in the worst case.
And, think about the kind of data, modern day computers deal with.
If this n is really large, if we take n= 2 to the power 64, and imagine that 1 comparison takes 1 milli second, then we will take 2 to the power 64 milli seconds.
If you try to convert this to seconds, hours, days and so on, this will amount to some years.
If our list however is sorted, we can us something called binary search, and with binary search it the size of the list is n, it will take only log of n to the base 2 comparisons to perform a search.
So, if n is equal to 2 to the power 64, we will take only 64 milliseconds.
I had taken n equal 2 to the power 64 earlier, to be able to perform this log quickly.

Sorting as a problem is well studied and a great deal of research has gone into devising efficient algorithms for sorting.

In this series of lessons we are going to study, analyze, and compare these sorting algorithms.

Some of the sorting algorithms that we will be talking about, that we will be analyzing about are Bubble Sort, Selection sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort and this is not all.
There are more.

And, you can imagine how important sorting as a problem is.
We have so many algorithms for sorting that have been designed over a period of time.

Classifiaction

We often classify sorting algorithms based on some parameters.
The first parameter that we want to classify upon is time complexity which is the measure of rate of growth of time taken by an algorithm with respect to input size.

Some algorithms will be relatively faster than others.
The second parameter that we use for classification is space complexity or memory usage.
Some sorting algorithms are in place, they use constant amount of extra memory to rearrange the elements in the list, while some sorting algorithms like merge sort, use extra memory to temporarily store data and the memory usage grows with input size.

The third parameter that we talk about is stability and this one will take some explanation.

A stable sorting algorithm in the case of equality of key, or the property upon which we are sorting, preserves the relative order of elements.
So, if the key is equal, if an element was coming before in the original list, it will also come before in the sorted list.
A stable sorting algorithm guarantees that.

The next parameter of classification is whether a sort is internal sort or external sort.

When all the records that need to be sorted in the main memory or RAM, then such sort is internal sort and if the records are on auxiliary storage like disk and tapes, quite often because it's not possible to get all of them in the main memory in one go, then we call such a sort external sort.

There is one more parameter upon which we may classify sorting algorithms, and it is whether algorithm is recursive or non recursive.

Some sorting algorithms like Quick Sort and Merge Sort are recursive while other like Insertion Sort and Selection sort are non-recursive.
We will study all these properties in detail as we will study these individual algorithms.
This is it for a basic introduction.