Category: Sort
Quick Select & Quick Sort
Posted on
Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance. Quick Sort is an unstable sort. It has amortized…
Merge Sort
Posted on
Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem If is of complexity , then is of complexity So in these problems, a key point…