Why do we need to learn different sorting algorithms?

Sorting is one of the fundamental coding problems in data structure and algorithms. The critical question is: why do we study the design and analysis of the sorting algorithms? Here are some critical reasons:

Reason 1: We can learn various problem-solving approaches using sorting algorithms

The sorting problem can be solved using various ideas. So sorting algorithm is one of the best ideas to learn different problem-solving approaches. For example: 

Incremental approach: Bubble sort, Selection, and Insertion sort are based on this idea where we incrementally build a partial solution. At each outer loop iteration, we place one value to the correct position on the sorted output. In other words, at each iteration of the outer loop, the unsorted sort will decrease by 1, and the partially sorted array size will increase by 1.

Divide and conquer: Merge sort and Quicksort are the fastest sorting algorithms based on the divide and conquer approach. Using a similar idea, we can solve several coding problems efficiently.

Two pointers approach: The merging process in the merge sort and the partition process in quicksort are good examples of the two pointers approach. We move both pointers forward and build the partial solution based on the condition.

Problem-solving using a data structure: Heap sort and BST sort are good examples. In the heap sort, we first build the max-heap structure of the input and continuously perform the deletion of the max element with the heapify operation. Similarly, in the BST sort, we first create a BST of the given input and traverse the tree using in-order traversal to generate the sorted output. The good thing is that both sorting algorithms work in O(nlogn) time complexity. On the other side, linear time sorting algorithms like counting sort and bucket sort use the direct addressing idea of hashing to sort the input given in a particular range.

Reason 2: We can use sorting to solve several coding problems

Sometimes, organizing the data into sorted order can help us solve coding problems efficiently. In other words, sorting is also a problem-solving approach in DSA. For example, after organizing the data in sorted order, we can perform a single scan, apply a binary search, or use a two-pointers approach to get the desired output.

Sometimes, we inherently need sorting algorithms in our applications. For example, contact numbers are organized in sorted order of name on mobile phones. Similarly, several algorithms use sorting as a subroutine for their solution. For example, advanced algorithms like "finding the closest pair of points" and "finding convex hull" use sorting to pre-process input.

Here is some problem that uses sorting:

• Check for pair in an array with a given sum
• Check whether an array is a subset of another array
• Find the most frequent element in an array
• Find longest consecutive sequence in an Array
• Find first missing positive
• Find triplet with zero-sum in an array
• Check if two arrays are equal or not

Reason 3: Analysis of sorting algorithms is the best idea to learn analysis of algorithms

Sorting is one of the best algorithms to learn recursion and iteration's time and space complexity analysis. For example, analysis of Bucket sort, Insertion sort, Selection sort, Heap sort, and Counting sort are good ideas to learn the best, worst and average case analysis of various types of loops. Similarly, analysis of merge sort and quick sorts are good ideas for learning recursion analysis.

Reason 4: Sorting is a good problem to understand several variations of a coding problem, boundary conditions, and code optimization techniques

Other than organizing data in increasing or decreasing order, there are a lot of variations available to the sorting problems. On the other hand, sorting algorithms are good to learn: how to handle several boundary conditions (base case, initialization, termination, post-termination situation, a scenario of repeated elements, etc.) in iterative and recursive code.

Here are some popular variations of sorting problems:

• Sort Characters by Frequency
• Sort a Stack using Stack
• Sort an array in a waveform
• Sort an array of 0s, 1s, and 2s
• Topological sorting in a graph
• Sort Array by parity
• Sort an array according to the order defined by another array
• Sort even-placed elements in increasing and odd-placed in decreasing order

Sorting algorithms are good ideas to learn code optimization approaches. For example, we can optimize bubble sort code using a flag variable, insertion sort code using binary search, quick-sort code using the idea of insertion sort, etc.

Enjoy learning, Enjoy sorting!