Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.

The counting sort algorithm assumes that each n input element is an integer in the range 0 to k. So by using array indexing as a tool for determining relative order, counting sort can sort n numbers in O(k + n) time when k = O(n). In other words, counting sort is one of the popular linear time sorting algorithms that works in O(n) time complexity if input elements are an integer in the range 0 to k.

These are some critical reasons to study sorting algorithms: 1) It can help us to learn analysis of algorithms and various problem-solving approaches 2) Sorting can work as a problem-solving approach to solve several coding problems 3) We can learn code optimization techniques and variations in boundary conditions using sorting.

Comparison-based sorting algorithms like merge sort, quicksort, insertion sort, heap sort, etc., determine the sorted order based on the comparisons between the input elements. We call such algorithms comparison sort. The critical question is: Why is the lower bound of comparison sort O(nlogn)? Explore this blog to get an answer!

Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best searching problems for learning step-by-step optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate correct output.

Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.

Given a stack, write a program to sort the stack in ascending order. We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are push(s, x), pop(s), top(s), isEmpty(s).

Given an unsorted array X[] of distinct elements, write a program to find the maximum j  -  i such that j > i and X[j] > X[i].

Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.

Comparison of sorting algorithms based on different parameters helps us choose an effcient sorting method in various problem-solving scenarios. You will get an answer to the following questions: how to compare two sorting algorithms? Which sorting is best in terms of properties like efficiency, in-place, stability, online vs. offline, etc.

Given two integer arrays X[] and Y[], write a program to check if the arrays are equal or not. Two arrays are equal if they have the same elements in any order. If there are repeated elements, then counts of repeated elements must also be the same for both arrays.

Given an array X[] of n integers, write a program to find the length of the longest consecutive elements sequence. In other words, we need to find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers. The consecutive numbers can be in any order.

Given an array X[] of size n, write a program to find the most frequent element in the array, i.e. the element which occurs the most number of times. It is assumed that at least one element is repeated.

We are given two integer arrays X[] and Y[], write a program to check whether array Y[] is a subset of array X[] or not. An array Y is a subset of another array X if each Y element is present in X. How do you check if one array is a subset of another? Explore and Enjoy!

Given an array of n integers and a target number, write a program to check whether a pair sum exits in the array or not. In other words, we need to check whether pair of elements in the array sum exactly to the target value.

Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!

Sorting algorithms are the most fundamental problems to study in data structure and algorithms. But the critical question is - why we learn the design, code, and analysis of the sorting algorithms? Explore and Think!

Given an array X[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order. This is a famous coding interview problem asked in facebook, microsoft and amazon.

Given an array of integers, sort the array into a wave-like arrangement. In other words, An array A[0..n-1] is sorted in wave form if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= ….This problem has been asked during google coding interview.