Sort

TL;DR Merge sort use Divide and Conquer strategy Repeatedly divides the array into two subarrays until subarrays of size 1 Merge two sorted array to achieve a bigger sorted array Time complexity is $O(n \log n)$ Space complexity is $O(n)$ (non-inplace) How Merge Sort Works?

2021-04-06

TL;DR Divide and Conquer (D&C) Partition the array with the selected pivot: [elements <= pivot, pivot, elements > pivot]. Recursively apply quick sort on left and right sub-arrays. Average time complexity: $O(n \log n)$ 💡 Idea Pick a pivot Partition the array into two sub-arrays Elements less thant the pivot go to the left sub-array Elements greater thant the pivot go to the right sub-array Call quick sort recursively on the two sub-arrays Concat left sub-array, pivot, and right sub-array Implementation Quick sort can be implemented using Divide and Conquer (D&C).

2021-04-06

TL;DR Key idea: repeatedly selecting the smallest remaining item Time complexity: $O(n^2)$ Idea The idea of selection sort is pretty simple: First, find the smallest item in the array and exchange it with the first entry Then, find the next smallest item and exchange it with the sec- ond entry.

2021-04-06