My Top 3 Sorting Algorithms

Sorting is nothing complicated just the rearranging of data in ascending or descending order and if you ask a person without a Computer science background, he will not even think about it for a second.

But a CS professional does not get paid to do things a common man can do in a second and hence there are many types of algorithms for sorting some for better time or space complexity in certain cases and some just to find a unique way to problem.

As a Second-year student I have been taught around 10 sorting algorithms and I would like to talk about the top 3 algorithms according to me and not just only regarding time and space complexity because there are already many sources for that on the web.

1.

The first algorithm I would like to talk about is Insertion sort with O(n²) as worst case. This algorithm has the worst complexity of others in the list but as a programmer I prefer codes which are easier to code and explain to the common people as I think there is more chance of confusion in a code than getting the worst time complexity case.

The above is the code for insertion sort and it is not the easiest to code as bubble sort takes that place but if one must explain these codes one would think as Insertion sort as a more practical approach as an element is inserted into the right position in the sorted part of the array same as sorting a deck of cards.

But if a common person is explained bubble sort, he might lose hope in software engineers as comparing every element to every other element in the array just doesn’t seem as practical approach.

The reason I personally like this sort is that it is great entry point for students to enter the world of sorting algorithms and was one of the first sorting algorithms I was taught.

This sort is also used in the default sort function in C++ which uses introsort a hybrid of quick sort and heap sort and insertion sort applied to the result.

2.

The second sort I prefer is Merge sort with O(nlogn) as the worst-case time complexity which is one of the best among the comparison sort.

Some of you might have a doubt that even though it has one of the best time complexity among comparison sort why isn’t it used as a method in the default sorting function in C++ and heap sort is preferred even though these have similar time complexities .The main reason for this is the huge difference in their worst case space complexity as heap sort which uses a binary tree to sort doesn’t take much space and has a space complexity of O(1) whereas Merge sort where a array is broken down to its single element for n elements has a relatively poor space complexity of O(n) and hence is not preferred over heap sort.

This code might seem complex compared to Insertion sort and it is but it uses one of the most important concepts used in algorithms which is divide and conquer and is used in many problems like min-max problem, Strassen problem and closest pair problem. This concept is also used in binary sort and is one of the most important concepts in computer science.

The basic concept of this algorithm is simple keep on dividing the array till there are n elements and while merging these elements these are merged in form of sorted array until a array with n elements is formed which will be in a sorted order shown in the image below and was my introduction to the divide and conquer which was very important for binary search.

3.

The Third algorithm which made me activate my brain cell is counting sort. What if you had to sort a set of test paper on basis of marks of your classmate. The obvious approach would be comparing each paper with every other one (Bubble sort), the practical approach would be to form a sorted set and insert the next paper in the correct order by comparing it with the ordered stack (Insertion sort) or better you have huge table paper where you split the stack into individual papers and then merge them by comparing the stacks to form a sorted stack (Merge Sort).

All these sorts have one thing in common which is the word comparing and what if I told you there is sorting algorithm which doesn’t require comparing you would be shocked and so was I when I heard about counting sort.

The above is the code of counting sort which is complicated and tough to understand hence we will continue with example of sorting the test papers.

For purpose of easy understanding let’s think that this was a test of 5 marks and to sort this you bring 6 boxes with numbers 0,1,2,3,4,5 on it and every time you find marks in the original stack of test papers you add a ball in the corresponding box with the value of marks written on it. This will be done for the whole stack.

After this is done the same number of balls in box 0 will be added to box 1 and the number of balls in box 1 will be added to box 2 and so on. Finally, the number of balls in a box will show the correct sorted position in the original array the same thing is shown in the image below.

This sorting I think was one of the best I have learnt about not only because of its low time complexity of O(n+k) but because of its uniqueness and the thought that was put into it to devise such a sorting algorithm that doesn’t need comparison greatly reducing time complexity in some cases.

I would like to conclude by saying that these were the 3 sorting algorithms I found easy to understand and code and were helpful and interesting to learn and think about. These are definitely not the best according to usage and complexity but I hope that these help you get interested in sorting algorithms.