One Pager Cheat Sheet
- We will learn how to use the
Divide-and-Conquer
approach and apply it to sort an array inO(N log N)
complexity using Max & Min Heaps. - Merge Sort is an efficient
divide and conquer
algorithm that breaks down lists into smaller sublists, sorts them, and then merges them in order to create a fully sorted list. - The MergeSort algorithm can be implemented using two functions -
merge_sort(array, startIndex, lastIndex)
andmerge(array, startIndex, middle, lastIndex)
, which divides and merges sub-arrays. - The sorting of an array of size
N
using Merge Sort has a worst-case time complexity ofO(N log N)
. - The worst-case time complexity of MergeSort is
O(N logN)
, resulting from the merging ofN
elements and the splitting of each element intologN
parts. - The Quick Sort algorithm is based on the
divide and conquer
technique, whereby apivot
element is chosen, and the array is divided into two sides, with elements on the left being smaller than the pivot, and elements on the right being greater. - Quick Sort can
be implemented
using two functions,partition
andquick_sort
, to divide and re-arrange elements in the array based on a selected pivot. - Quick sort reduces the
space complexity
and improves thetime complexity
by using an random pivot selection from the array, compared to merge sort. - Quick Sort uses a
partitioning
process to split the unsorted array around a randomly chosen pivot element and recursively sort the subarrays. - Heap Sort is an improved version of
selection sort
which views theArray
as a Max-Heap and utilizes aheapify
function to put the elements in their correct positions. - The
heapify
andheapSort
functions are used to implement Heap Sort in C++. - The
heapify
function can only be used on non-leaf nodes to convert them to aMax-Heap
, as leaf nodes have no children to be converted. - Heap sort has a time complexity of
O(N log N)
, but is not stable. - Both Merge Sort and Quick Sort are popular sorting algorithms based on the
divide-and-conquer
principle, where a problem is broken down into smaller sub-problems and then combined to get the desired result.