# Sorting

## Sorting

## 1. Count Sort

Time: O(n), Space: O(n)

```java
public static void countSort(int[] nums) {
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

    for (int num : nums) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    int[] count = new int[max - min + 1];
    for (int num : nums) {
        ++count[num - min];
    }

    int index = 0;
    for (int i = min; i <= max; i++) {
        while (count[i - min] > 0) {
        nums[index] = i;
        ++index;
        --count[i - min];
        }
    }
}
```

## 2. Bucket Sort

Time: O(n + k), Space: O(n)

```java
// To be continued
```

## 3. Quick Sort

Time: O(nlogn), Space: O(logn)

```java
    public static void quickSort(int[] nums) {
        recQuickSort(nums, 0, nums.length - 1);
    }

    public static void recQuickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(nums, start, end);
        recQuickSort(nums, start, pivot - 1);
        recQuickSort(nums, pivot + 1, end );
    }

    public static int partition(int[] nums, int start, int end) {
        // Use the middle element as pivot
        int pivot = (start + end) >> 1;
        // Put the pivot to the end
        swap(nums, pivot, end);

        // Put element smaller than the pivot to the first half of array
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                swap(nums, i, start);
                ++start;
            }
        }
        // Put the pivot back to position it should be in after partition
        swap(nums, start, end);
        return start;
    }

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

* Quick Select (Find the Kth Largest/Smallest Number)

```java
   public int quickSelect(int[] nums, int k, int start, int end) {
        int pivot = partition(nums, start, end);

        if (pivot < k) {
            return quickSelect(nums, k, pivot + 1, end);
        }
        else if (pivot > k) {
            return quickSelect(nums, k, start, pivot);
        }
        else {
            return nums[pivot];
        }
    }

    public int partition(int[] nums, int start, int end) {
        int mid = (start + end) >> 1;
        swap(nums, mid, end);

        for (int i = start; i < end; i++) {
            // To get the Kth largest number, put element larger than the pivot to the left 
            if (nums[i] > nums[end]) {
                swap(nums, start, i);
                ++start;
            }
        }
        swap(nums, start, end);
        return start;
    }

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

## 4. Merge Sort

Time: O(nlogn), Space: O(n)

```java
    public void mergeSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        mergeSort(nums, 0, nums.length - 1);
    }

    public void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;

        while (i <= mid || j <= end) {
            if (i > mid || (j <= end && nums[j] < nums[i])) {
                temp[k++] = nums[j++];
            }
            else {
                temp[k++] = nums[i++];
            }
        }

        for (int index = 0; index < k; index++) {
            nums[start + index] = temp[index];
        }
    }
```

## 5. Questions

* Merge Sort: [Reverse Pairs, ](https://leetcode.com/problems/reverse-pairs/?tab=Description%29%20\[Count%20of%20Smaller%20Numbers%20After%20Self]%28https://leetcode.com/problems/count-of-smaller-numbers-after-self/?tab=Description)
* Quick Sort: [Kth Largest Element in an Array, ](https://leetcode.com/problems/kth-largest-element-in-an-array/?tab=Description%29%20\[Sort%20Colors,%20]%28https://leetcode.com/problems/sort-colors/?tab=Description%29\[Move%20Zeroes]%28https://leetcode.com/problems/move-zeroes/?tab=Description) [Wiggle Sort II](https://leetcode.com/problems/wiggle-sort-ii/description/)
* Count Sort: [Sort Colors](https://leetcode.com/problems/sort-colors/?tab=Description),  [H-Index](https://leetcode.com/problems/h-index/description/)
* Bucket Sort: [Sort Characters By Frequency, ](https://leetcode.com/problems/sort-characters-by-frequency/?tab=Description) [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/?tab=Description),  [Maximum Gap](https://leetcode.com/problems/maximum-gap/description/)
