In this post, we are going to discuss all the sorting algorithms with either the best case or worst case or average-case time complexity as O(nlogn).
MergeSort
MergeSort is a Divide and Conquer based algorithm. MergeSort works by repeatedly diving the input array into subarray until each subarray doesn’t have only 1 element and then merging those subarrays in such a way that, the final result of combination is a sorted list.
The Best, Average, and Worst case time complexity of MergeSort is O(nlogn)
Read up on how to implement a merge sort algorithm here.
QuickSort
Quicksort is a Divide and conquer based algorithm that picks a pivot element from the given array and partition(rearranges) the array in such a way that elements in subarray before pivot are less than or equal to the pivot and element in subarray after pivot are greater than pivot(but not necessarily in sorted order).
The Best and Average case time complexity of QuickSort is O(nlogn) but the worst-case time complexity is O(n²).
Read up on how to implement a quick sort algorithm here.
HeapSort
Heapsort is a comparison based sorting technique based on a Binary Heap data structure. It is similar to the selection sort. It works by dividing the input into a sorted and an unsorted region, and it iteratively extracting the largest element from the unsorted region and inserting it into the sorted region.]
The Best, Average, and Worst case time complexity of MergeSort is O(nlogn)
Read up on how to implement a quick sort algorithm here.
That concludes our post. MergeSort and HeapSort algorithms have O(nlogn) time in Best, Average & Worst case, while Quick sort has O(nlogn) time complexity only in Best and Average Case.
