One Pager Cheat Sheet

• We will learn how to use the Divide-and-Conquer approach and apply it to sort an array in O(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) and merge(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 of O(N log N).
• The worst-case time complexity of MergeSort is O(N logN), resulting from the merging of N elements and the splitting of each element into logN parts.
• The Quick Sort algorithm is based on the divide and conquer technique, whereby a pivot 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 and quick_sort, to divide and re-arrange elements in the array based on a selected pivot.
• Quick sort reduces the space complexity and improves the time 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 the Array as a Max-Heap and utilizes a heapify function to put the elements in their correct positions.
• The heapify and heapSort functions are used to implement Heap Sort in C++.
• The heapify function can only be used on non-leaf nodes to convert them to a Max-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.