10 Best Sorting Algorithms You Must Know About

Types of Sorting in Data Structures
Comparison-based sorting: In comparison-based sorting techniques, a comparator is defined to compare elements or items of a data sample. This comparator defines the ordering of elements. Examples are: Bubble Sort, Merge Sort.
Counting-based sorting: There's no comparison involved between elements in these types of sorting algorithms but rather work on calculated assumptions during execution. Examples are : Counting Sort, Radix Sort.
In-Place vs Not-in-Place Sorting: In-place sorting techniques in data structures modify the ordering of array elements within the original array. On the other hand, Not-in-Place sorting techniques use an auxiliary data structure to sort the original array. Examples of In place sorting techniques are: Bubble Sort, Selection Sort. Some examples of Not in Place sorting algorithms are: Merge Sort, Quick Sort.
Finally, we'll wrap up with a broad-spectrum analysis as to which algorithm stands out in terms of time and space complexities.
Sorting Algorithms in Java vs C++
Java is the most popular language of choice when it comes to implementing algorithms and working with data structures in the software industry.
Level up your foundational programming skills in Java and practice the most relevant Data Structure questions in Crio's Backend Developer Program. Check out the full syllabus here >>
Although this blog focuses heavily on C++ based implementations, don't fret because as long as your logical understanding of these algorithms is strong, the only thing holding you back is basic syntactic differences between Java and C++.
Need guidance with problem-solving and data structures? Go through Crio's Data Structures Track and unlock what it takes to tackle unseen problems with ease.
Top 10 Sorting Algorithms You Need To Know
10 Best Sorting Algorithms
1. Bubble Sort
The basic idea of bubble sorting is that it repeatedly swaps adjacent elements if they are not in the desired order. YES, it is as simple as that.
If a given array of elements has to be sorted in ascending order, bubble sorting will start by comparing the first element of the array with the second element and immediately swap them if it turns out to be greater than the second element, and then move on to compare the second and third element, and so on.
Understanding Bubble Sort algorithm with a simple example
Let's try to understand the intuitive approach behind bubble sort with an example:
Bubble sort algorithm explained
Now that you've understood the intuitive idea behind bubble sort, it's time to take a look at its standard C++ implementation.
Use Cases
It is used to introduce the concept of a sorting algorithm to Computer Science students.
In computer graphics, bubble sorting is quite popular when it comes to detecting a very small error (like swap of just two elements) in almost-sorted arrays.
Try it yourself
Q. Given an array of n input integers, return the sum of maximum and minimum elements of the array. [Constraint: Use Bubble Sorting]
Input:
n -> Size of array (n>1)
'n' array elements below
Output: A single line representing the required sum
P.S: Don't forget to drop a comment below if you face issues with this problem.
2. Selection Sort
Selection sort is a sorting algorithm in which the given array is divided into two subarrays, the sorted left section, and the unsorted right section.
Initially, the sorted portion is empty and the unsorted part is the entire list. In each iteration, we fetch the minimum element from the unsorted list and push it to the end of the sorted list thus building our sorted array.
3. Insertion Sort
Insertion sort is a sorting algorithm in which the given array is divided into a sorted and an unsorted section. In each iteration, the element to be inserted has to find its optimal position in the sorted subsequence and is then inserted while shifting the remaining elements to the right.
Use Cases
This algorithm is stable and is quite fast when the list is nearly sorted.
It is very efficient when it comes to sorting very small lists (example say 30 elements.)
Try it yourself
Q. Given a list of numbers with an odd number of elements, find the median? [Constraint: Use Insertion Sort]
Input:
n -> Size of array (n>0)
'n' array elements below
Output: A single line representing the required median.
P.S: Don't forget to share your approach with us in the comments below!
4. Quick Sort
Quick Sort is a divide and conquer algorithm. The intuitive idea behind quick sort is it picks an element as the pivot from a given array of elements and then partitions the array around the pivot element. Subsequently, it calls itself recursively and partitions the two subarrays thereafter.
Understanding Quick Sort algorithm with a visualization
Quick sort algorithm explained
The logical steps involved in Quick Sort algorithm are as follows:
Pivot selection: Picks an element as the pivot (here, we choose the last element as the pivot)
Partitioning: The array is partitioned in a fashion such that all elements less than the pivot are in the left subarray while all elements strictly greater than the pivot element are stored in the right subarray.
Recursive call to Quicksort: Quicksort function is invoked again for the two subarrays created above and steps are repeated.
Comments have been included in the implementation below to help you understand the Quick Sort algorithm better.
Use Cases
Quick Sort is probably more effective for datasets that fit in memory.
Quick Sort is appropriate for arrays since is an in-place sorting algorithm (i.e. it doesn’t require any extra storage)
Try it yourself
Q. Given a list of numbers with an odd/even number of elements, find the median? [Constraint: Use Quick Sort]
Input:
n -> Size of array (n>0)
'n' array elements below
Output: A single line representing the required median.
P.S: Need a hint? Drop a comment below.
5. Merge Sort
Merge Sort is a divide-and-conquer algorithm. In each iteration, merge sort divides the input array into two equal subarrays, calls itself recursively for the two subarrays, and finally merges the two sorted halves.
7. Radix Sort
As you saw earlier, counting sort stands apart because it's not a comparison-based sorting algorithm like Merge Sort or Bubble Sort, thereby reducing its time complexity to linear time.
BUT, counting sort fails if the input array ranges from 1 to n^2 in which case its time complexity increases to O(n^2).
The basic idea behind radix sorting is to extend the functionality of counting sort to get a better time-complexity when input array elements range from 1 till n^2.
Understanding Radix Sort with an example
Algorithm:
For each digit i where i varies from the least significant digit to the most significant digit of a number, sort input array using count sort algorithm according to the ith digit. Remember we use count sort because it is a stable sorting algorithm.
Example:
Radix sort algorithm explained
Thus we observe that radix sort utilizes counting sort as its subroutine throughout its execution. Now take a look at its C++ implementation.
Use Cases
It is also used in the DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
Try it yourself:
Q. Given two sorted arrays(arr1[] and arr2[]) of size M and N of distinct elements. Given a value Sum. The problem is to count all pairs from both arrays whose sum is equal to Sum.
Note: The pair has an element from each array. [Constraint: Use Radix Sort]
Input:
n -> Size of array (n>1)
'n' array elements below
Output: A single line representing the required number of pairs
P.S: Don't forget to share your approach with us in the comments below.
8. Bucket Sort
Bucket Sort is a comparison-based sorting technique that operates on array elements by dividing them into multiple buckets recursively and then sorting these buckets individually using a separate sorting algorithm altogether. Finally, the sorted buckets are re-combined to produce the sorted array.
Understanding Bucket Sort algorithm with pseudocode
We can probe further into the working of bucket sort by assuming that we've already created an array of multiple 'buckets' (lists). Elements are now inserted from the unsorted array into these "buckets" based on their properties. These buckets are finally sorted separately using the insertion sort algorithm as explained earlier.
Pseudocode:
Begin
for i = 0 to size-1
insert array[i] into the bucket indexed (size * array[i])
done
for i = 0 to size-1
sort bucket[i] using insertion sort
done
for i = 0 to size-1
Combine items of bucket[i] and insert in array in sorted order
done
End
Well if you're still unsure about the bucket sort algorithm, go back and review the pseudocode one more time.
Use Cases
Bucket sorting is used when input is uniformly distributed over a range.
It is also used for floating point values.
Try it yourself
Q. You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed. [Constraint: Use Bucket Sort]
Input:
n -> Size of array (n>1)
'n' array elements representing the first array
'n' array elements representing the second array
Output: A single line representing the required sum
P.S: Need help? Drop a comment below.
9. Comb Sort
Comb sort is quite interesting. In fact, it is an improvement over the bubble sort algorithm. If you've observed earlier, bubble sort compares adjacent elements for every iteration.
But for comb sort, the items are compared and swapped by a large gap value. The gap value shrinks by a factor of 1.3 for each iteration until the gap value reaches 1, at which point it stops execution.
Use Cases
Comb Sort eliminates small values at the end of the list by using larger gaps.
Itis a significant improvement over Bubble Sort.
Try it yourself
Q. Given an array, find the most frequent element in it. If there are multiple elements that appear maximum number of times, print any one of them. [Constraint: Use Comb Sort]
Input:
n -> Size of array (n>0)
'n' array elements below
Output: A single line representing the element with maximum frequency.
P.S: Did you enjoy this sorting technique? Share your opinions below.
10. Shell Sort
Shell sort algorithm is an improvement over the insertion sort algorithm wherein we resort to diminishing partitions to sort our data.
In each pass, we reduce the gap size to half of its previous value for each pass throughout the array. Thus for each iteration, the array elements are compared by the calculated gap value and swapped (if necessary).
Q1. Which is the best sorting algorithm?
But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
At the end of the day though, the best sorting algorithm comes down to the nature of your input data (and who you ask).
Q2. What is the easiest sorting algorithm?
Bubble sort is widely recognized as the simplest sorting algorithm out there. Its basic idea is to scan through an entire array and compare adjacent elements and swap them (if necessary) until the list is sorted. Pretty simple right?
Q3. Which sorting algorithm would you prefer for nearly sorted lists?
When it comes to sorting nearly sorted data, insertion sort is the clear winner particularly because it's time complexity reduces to O(n) from a whopping O(n^2) on such a sample.
On the other hand, merge sort or quick sort algorithms do not adapt well to nearly sorted data.
Well, that's about it. At the end of the day, it's up to you to decide which sorting technique suits you the best. And yes, don't forget to try out the practice problems served alongside with each sorting technique.
How comfortable are you with sorting now?
Before you go for your next interview, be sure to know the answers to these commonly asked Sorting Algorithms questions. If you read this blog thoroughly, you're all set to get a perfect score. Ready to take the quiz?
Go beyond video-based certification courses and online bootcamps. Build the confidence you need to take on Data Structures and Algorithm questions in your next big interview and land your dream job as a Backend Developer or Full Stack Developer - Guaranteed! Find out how.
Additional resources
Don't miss these free learning resources that are an absolute essential for all developers: