Sorting Algorithms

Algorithm Algorithm Gist Time Complexity
Merge Sort Merge sort is based on divide and conquer strategy. Uses extra space for sorting.
The array is split all the way down to single elements before merging which occurs during way out.
Thus it exhibits bottom-up recursion.
Best-case : O(nlogn)
Worst-case : O(nlogn)
Average-case : O(nlogn)
Quick Sort Quick sort is based on divide and conquer strategy.
It is an in-place sorting algorithm (no additional space required for sorting).
Array partitioning and the main task of sorting happens before the recursive calls. Thus it exhibits top-down recursion.
Best-case : O(nlogn)
Worst-case : O(n^2)
Average-case : O(nlogn)

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.