7 Sorting Algorithms (quick sort, top-down/bottom-up merge sort, heap sort, etc.)
7 Sorting Algorithms:\n1. quick sort\n2. top-down merge sort\n3. bottom-up merge sort\n4. heap sort\n5. selection sort\n6. insertion sort\n7. bubble sort (TLE)\
7 Sorting Algorithms:\n1. quick sort\n2. top-down merge sort\n3. bottom-up merge sort\n4. heap sort\n5. selection sort\n6. insertion sort\n7. bubble sort (TLE)\n\nThe implementations are as below:\n1. quick sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        quickSort(nums, 0, nums.length - 1);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void quickSort(int[] nums, int l, int r) {\n        if (l >= r) return;\n        int mid = partition(nums, l, r);\n        quickSort(nums, l, mid);\n        quickSort(nums, mid + 1, r);\n    }\n    private int partition(int[] nums, int l, int r) {\n        int pivot = nums[l];\n        while (l < r) {\n            while (l < r && nums[r] >= pivot) r--;\n            nums[l] = nums[r];\n            while (l < r && nums[l] <= pivot) l++;\n            nums[r] = nums[l];\n        }\n        nums[l] = pivot;\n        return l;\n    }\n}\n```\n\n2. top-down merge sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        mergeSort(nums, 0, nums.length - 1);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void mergeSort(int[] nums, int l, int r) {\n        if (l >= r) return;\n        int mid = l + (r - l) / 2;\n        mergeSort(nums, l, mid);\n        mergeSort(nums, mid + 1, r);\n        merge(nums, l, r);\n    }\n    private void merge(int[] nums, int l, int r) {\n        int mid = l + (r - l) / 2;\n        int[] tmp = new int[r - l + 1];\n        int i = l, j = mid + 1, k = 0;\n        while (i <= mid || j <= r) {\n            if (i > mid || j <= r && nums[i] > nums[j]) {\n                tmp[k++] = nums[j++];\n            } else {\n                tmp[k++] = nums[i++];\n            }\n        }\n        System.arraycopy(tmp, 0, nums, l, r - l + 1);\n    }\n}\n```\n\n3. bottom-up merge sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        mergeSort2(nums);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void mergeSort2(int[] nums) {\n        for (int size = 1; size < nums.length; size *= 2) {\n            for (int i = 0; i < nums.length - size; i += 2 * size) {\n                int mid = i + size - 1;\n                int end = Math.min(i + 2 * size - 1, nums.length - 1);\n                merge2(nums, i, mid, end);\n            }\n        }\n    }\n    private void merge2(int[] nums, int l, int mid, int r) {\n        int[] tmp = new int[r - l + 1];\n        int i = l, j = mid + 1, k = 0;\n        while (i <= mid || j <= r) {\n            if (i > mid || j <= r && nums[i] > nums[j]) {\n                tmp[k++] = nums[j++];\n            } else {\n                tmp[k++] = nums[i++];\n            }\n        }\n        System.arraycopy(tmp, 0, nums, l, r - l + 1);\n    }\n}\n```\n\n4. heap sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        heapSort(nums);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void heapSort(int[] nums) {\n        for (int i = nums.length / 2 - 1; i >= 0; i--) {\n            heapify(nums, i, nums.length - 1);\n        }\n        for (int i = nums.length - 1; i >= 1; i--) {\n            swap(nums, 0, i);\n            heapify(nums, 0, i - 1);\n        }\n    }\n    private void heapify(int[] nums, int i, int end) {\n        while (i <= end) {\n            int l = 2 * i + 1, r = 2 * i + 2;\n            int maxIndex = i;\n            if (l <= end && nums[l] > nums[maxIndex]) maxIndex = l;\n            if (r <= end && nums[r] > nums[maxIndex]) maxIndex = r;\n            if (maxIndex == i) break;\n            swap(nums, i, maxIndex);\n            i = maxIndex;\n        }\n    }\n    private void swap(int[] nums, int i, int j) {\n        int tmp = nums[i];\n        nums[i] = nums[j];\n        nums[j] = tmp;\n    }\n}\n```\n\n5. selection sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        selectionSort(nums);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void selectionSort(int[] nums) {\n        for (int i = 0; i < nums.length; i++) {\n            int minIndex = i;\n            for (int j = i + 1; j < nums.length; j++) {\n                if (nums[j] < nums[minIndex]) minIndex = j;\n            }\n            if (minIndex != i) swap(nums, i, minIndex);\n        }\n    }\n    private void swap(int[] nums, int i, int j) {\n        nums[i] = nums[i] ^ nums[j];\n        nums[j] = nums[i] ^ nums[j];\n        nums[i] = nums[i] ^ nums[j];\n    }\n}\n```\n\n6. insertion sort\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        insertionSort(nums);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void insertionSort(int[] nums) {\n        for (int i = 1; i < nums.length; i++) {\n            for (int j = i; j >= 1; j--) {\n                if (nums[j] >= nums[j - 1]) break;\n                swap(nums, j, j - 1);\n            }\n        }\n    }\n    private void swap(int[] nums, int i, int j) {\n        nums[i] = nums[i] ^ nums[j];\n        nums[j] = nums[i] ^ nums[j];\n        nums[i] = nums[i] ^ nums[j];\n    }\n}\n```\n\n7. bubble sort (TLE)\n```java\nclass Solution {\n    public List<Integer> sortArray(int[] nums) {\n        List<Integer> res = new ArrayList<>();\n        if (nums == null || nums.length == 0) return res;\n        bubbleSort(nums);\n        for (int i : nums) res.add(i);\n        return res;\n    }\n    private void bubbleSort(int[] nums) {\n        for (int k = nums.length - 1; k >= 1; k--) {\n            for (int i = 0; i < k; i++) {\n                if (nums[i] > nums[i + 1]) swap(nums, i, i + 1);\n            }\n        }\n    }\n    private void swap(int[] nums, int i, int j) {\n        nums[i] = nums[i] ^ nums[j];\n        nums[j] = nums[i] ^ nums[j];\n        nums[i] = nums[i] ^ nums[j];\n    }\n}\n```
['Sorting', 'Merge Sort', 'Java']