TL;DR

Best solution for Top k smallest, Top k largetest, Top k frequency...problems, Time complexity : O(n), worst O(n^2)

Quick Sort

• Time complexity : O(nlogn) in the average case, space: O(1)
• in-place sort

https://stackoverflow.com/questions/12454866/how-to-optimize-quicksort

Quick-sort()
      choose a pivot
      move the smaller elements from left
      move the bigger elements from right
      quick-sort on the bigger half of the array

      if half is less then X
         only then do an insertion sort on the other half <- this is a tail recursion insertion sort 
      else
         quick sort on this half also

https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort

import java.util.Arrays;

public class QuickSort {
    // quickSort
    public void quickSort(int nums[], int left, int right) {
        if (left >= right) return;

        int pivot = partition(nums, left, right);

        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    private int partition(int nums[], int left, int right) {
        int pivot = right, storedIndex = left;

        for (int i = left; i < right; i++) {
            if (nums[i] < nums[pivot]) {
                swap(nums, i, storedIndex); // 把比 pivot 小的都移到左邊（左小
                storedIndex++;
            }
        }
        swap(nums, storedIndex, pivot); // 最後, swap pivot 到中間點 （左小 右大）
        return storedIndex; // get pivot index
    }

    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] num = {9, 4, 1, 6, 7, 3, 8, 2, 5};
        new QuickSort().quickSort(num, 0, num.length - 1);
        System.out.println(Arrays.toString(num));
    }
}

partition

private int partition(int num[], int begin, int end) {
...
	return counter; // get pivot index
}