Hello there! In this article we are going to discuss those some essential topics related to the general paradigm of Sorting . Sorting is an important topic from the point of view of placements and is frequently asked topic in interviews. The knowledge of different sorting algorithms, their time complexity and applications is a must .

The Basics —

Common Sorting Algorithms namely -

Bubble Sort — A basic sorting algorithm implemented simply using 2 for loops.This algorithm is the easiest one to implement.Idea — Loop through the array comparing adjacent elements,if they are out of order swap them. Repeat this until no swap occurs.

Selection Sort — Based on the idea of selecting the best available item one by one. Idea — Loop through the array and select the smallest available number and mark it unavailable.This will be the ith smallest element in the sorted array.Repeat this N times .

Insertion Sort — A basic sorting algorithm inspired by how sort playing cards in our hand.One by one select an element in the array.Create a new sorted array (initially empty)by inserting the selected element to its correct sorted position in the new array.

Note — Creating a new array is not necessary, and logic can be implemented in-place.(as we do when we sort playing cards )

If you want detailed tutorial on above algorithms MyCodeSchool videos are a great starting point.

Quick Sort — The most basic Random Algorithm.Introduces us to the capabilities and usefulness of random algorithms.

Idea — Randomly select a element, move all elements smaller than it to its front(in no particular order).Divide the array into two about pivot and repeat until array is sorted.

Side Topic-

Quickselect algorithm — Used to find ith greatest element in an array in O(n) average time. Idea— Randomly select a pivot element,move all elements smaller than it to its front. If the selected element is now at ith position stop,else recursively search either on the front array or back depending on i. Worst Case TC O(n²).

Merge Sort-The Most Basic Divide & Conquer algorithm.

Idea — Divide the array into two smaller array’s . Sort them somehow, then merge them easily. Well you need never sort any array , just keep on dividing the array into smaller arrays until array size is 1 which is by default sorted :) . So combine these 1 size sorted arrays to form 2 size sorted arrays and so on ..

Side Note — Learn about merging two sorted list into a single sorted list in O(N)

The Crucials —

Pro tip- In multiple cases sorting the input or queries or data makes the question relatively simpler to solve.so while solving a problem always think can sorting help me solve this problem ?

Write custom comparators — This is the most crucial part which requires some practice, the mastering of this topic is highly valuable in both coding rounds and interviews.

In case of sorting writing custom comparater is simple — Just write a comparison function, and add the function as a parameter in the inbuilt sort().

Example— Sort elements of array by frequency, if frequency is same print smaller number first.

Recommended- There is a great blog which discusses custom comparators in detail.

Ques — Counting inversions : Find number of pairs a[i] and a[j] in an array such that a[i] > a[j] and i < j.

Counting Number of inversion in an array is frequently asked question. We can solve it by modifying the merge part of Merge Sort algo.

Idea — While merging, we have pointers (i & j )pointing to current elements of both already sorted array. If a[i] is larger than a[j] then all elements in left array after a[i] will also be larger than a[j].

So number of inversion for a[j] is number of elements to the right of a[i] including a[i]. Detailed Solution.

Some Sort Algorithms used in the industry are:

Timsort — It is a hybrid sorting algorithm (combination of merge sort, insertion sort and additional logic) which is used in Android, Java, and Python.

Introsort — Another hybrid sorting algorithm(quicksort and heap sort) which is used internally in C++ sort function.

Some Terminologies related to Sorting-

Stable Sort — The sorting algo’s which don’t change the relative order of similar elements.The relative order of same numbers in input is preserved. ex- Insertion Sort, Merge Sort, Bubble Sort.

In-place Sorting — The sorting algo’s which don’t require extra space for sorting the elements. ex-Insertion Sort, Selection Sort, Bubble Sort.

Note — The lower bound of even the most efficient sorting algorithm will be O(n log n) time complexity for sort a general array.

The Pro Topics —

Counting Sort — Counting Sort is non-comparative sorting algorithm which uses extra space, and is helpful in scenarios when range of input is very less

Idea — Count frequency of each element occurring in array. Loop through the frequency array from smallest to largest , print each element the number of time it is occurring.

TC - O(n + R) , Space- O(R) (where R is range of possible values in array or R = max value in array — min value in array )

External Merge Sort ( K-way merge algorithm.)— Used when the array to be sorted is too large to be kept in memory.

Idea- Divide array into k small parts which can reside in memory and sort those individual parts. Then perform K-way merge on those k sorted arrays.

Note : Merging K sorted arrays is an important question in itself.

Side Note- HeapSort and TreeSort ,will be discussed in their relevant tutorials namely Heaps and Trees.

Practice Questions —

Tip : Try to come up with multiple solution for each of these questions

1. Swap two elements of an array without using extra space.

2. Check whether two strings are anagram of each other.

3. Sort an array according to the order defined by another array. Given two arrays: A1 and A2, sort A1 in such a way that the relative order among the elements in A1 will be same as those are in A2.

4. Find whether an array is subset of another array . Given two arrays: A1 and A2. Find whether A2 is a subset of A1 or not.Elements in both array are distinct.

5. Sort an array on 0’s,1’s and 2's