Java iterative/recursive quickSort, mergeSort, 3 ways quickSort, 3 ways mergeSort, max/min heapSort
Iterative quick sort\n\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return quickIterative(nums, 0, nums.length - 1);\n    }\n    \n    p
Iterative quick sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return quickIterative(nums, 0, nums.length - 1);\n    }\n    \n    private int[] quickIterative(int[] nums, int l, int h) {\n        if (l >= h) {\n            return nums;\n        }\n        // create a stack to store the low index and high index\n        int[] stack = new int[h - l + 1];\n        int top = 0;\n        // push low index and high index into stack\n        stack[top++] = l;\n        \n        stack[top++] = h;\n        \n        while (top > 0 ) {\n            // pop high and low\n            h = stack[--top];\n            l = stack[--top];\n            // partition, p is at the correct position\n            int p = this.partition(nums, l, h);\n            // if pivot\'s left side has array left, push into stack;\n            if (p - 1 > l) {\n                stack[top++] = l;\n                stack[top++] = p - 1;\n            }\n            // if pivot\'s right side has array left, push into stack;\n            if (p + 1 < h) {\n                stack[top++] = p + 1;\n                stack[top++] = h;\n            }\n            // keep doing this until the stack is empty;\n        }\n        return nums;\n    }\n    \n    private int partition(int[] nums, int head, int tail) {\n        int p_index = this.getMediumValueIndex(nums, head, tail);\n        int pivot = nums[p_index];\n        nums[p_index] = nums[tail];\n        nums[tail] = pivot;\n        p_index = tail;\n        int i = head - 1;\n        for (int j = head; j < tail; ++j) {\n            if (nums[j] <= pivot) {\n                i++;\n                int temp = nums[i];\n                nums[i] = nums[j];\n                nums[j] = temp;\n            }\n        }\n        int temp = nums[i+1];\n        nums[i+1] = nums[tail];\n        nums[tail] = temp;\n        return i + 1;\n    }\n    \n    \n    private int getMediumValueIndex(int[] nums, int head, int tail) {\n        int mid = head + (tail - head) / 2;\n        int l = nums[head];\n        int m = nums[mid];\n        int r = nums[tail];\n        if (l > m) {\n            // l > m > r\n            if (m > r) return mid;\n            // r > l > m\n            else if (r > l) return head;\n            //l > r > m\n            else return tail;\n        \n        } \n        // m > l\n        else {\n            // r > m > l\n            if (r > m) return mid;\n            // m > l > r\n            else if (l > r) return head;\n            // m > r > l\n            else return tail;\n        }\n    }\n}\n```\nStable iterative quick sort(TLE)\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return quickIterative(nums, 0, nums.length - 1);\n    }\n    \n    private int[] quickIterative(int[] nums, int l, int h) {\n        if (l >= h) {\n            return nums;\n        }\n        // create a stack to store the low index and high index\n        int[] stack = new int[h - l + 1];\n        int top = 0;\n        // push low index and high index into stack\n        stack[top++] = l;\n        \n        stack[top++] = h;\n        \n        while (top > 0 ) {\n            // pop high and low\n            h = stack[--top];\n            l = stack[--top];\n            // partition, p is at the correct position\n            int p = this.partition(nums, l, h);\n            // if pivot\'s left side has array left, push into stack;\n            if (p - 1 > l) {\n                stack[top++] = l;\n                stack[top++] = p - 1;\n            }\n            // if pivot\'s right side has array left, push into stack;\n            if (p + 1 < h) {\n                stack[top++] = p + 1;\n                stack[top++] = h;\n            }\n            // keep doing this until the stack is empty;\n        }\n        return nums;\n    }\n    \n    private int partition(int[] nums, int head, int tail) {\n        Queue<Integer> aux = new LinkedList<>();\n        Queue<Integer> left = new LinkedList<>();\n        Queue<Integer> right = new LinkedList<>();\n        for (int i  = head + 1; i <= tail; ++i) {\n            if (nums[i] < nums[head]) {\n                left.add(nums[i]);\n            } else {\n                right.add(nums[i]);\n            }\n        }\n        aux.addAll(left);\n        aux.add(nums[head]);\n        aux.addAll(right);\n        for (int i = head; i <= tail; ++i) {\n            nums[i] = aux.remove();\n        }\n        return head + left.size();\n    }\n    \n    private int getMediumValueIndex(int[] nums, int head, int tail) {\n        int mid = head + (tail - head) / 2;\n        int l = nums[head];\n        int m = nums[mid];\n        int r = nums[tail];\n        if (l > m) {\n            // l > m > r\n            if (m > r) return mid;\n            // r > l > m\n            else if (r > l) return head;\n            //l > r > m\n            else return tail;\n        \n        } \n        // m > l\n        else {\n            // r > m > l\n            if (r > m) return mid;\n            // m > l > r\n            else if (l > r) return head;\n            // m > r > l\n            else return tail;\n        }\n    }\n}\n```\n\n\nRecursive quick sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        if (nums.length <= 1) return nums;\n        this.qHelper(nums, 0, nums.length - 1);\n        return nums;\n    }\n    \n    private void qHelper(int[] nums, int head, int tail) {\n        if (head >= tail) return;\n        int pivot = this.partition(nums, head, tail);\n        this.qHelper(nums, head, pivot-1);\n        this.qHelper(nums, pivot+1, tail);\n    }\n    \n    private int partition(int[] nums, int head, int tail) {\n        // use the index with medium value as pivot point.\n        int pivot_index = this.getMediumValueIndex(nums, head, tail);\n        int pivot = nums[pivot_index];\n        // int temp = nums[pivot_index];\n        nums[pivot_index] = nums[tail];\n        nums[tail] = pivot;\n        pivot_index = tail;\n        int i = head - 1;\n        for (int j = head; j < tail; ++j) {\n            if (nums[j] < pivot) {\n                ++i;\n                //swap i and j\n                int temp = nums[i];\n                nums[i] = nums[j];\n                nums[j] = temp;\n            }\n        }\n        // swap i+1 and pivot_index\n        int temp = nums[i+1];\n        nums[i+1] = nums[pivot_index];\n        nums[pivot_index] = temp;\n        return i+1;\n        \n    }\n    \n    private int getMediumValueIndex(int[] nums, int head, int tail) {\n        int mid = head + (tail - head) / 2;\n        int l = nums[head];\n        int m = nums[mid];\n        int r = nums[tail];\n        if (l > m) {\n            // l > m > r\n            if (m > r) return mid;\n            // r > l > m\n            else if (r > l) return head;\n            //l > r > m\n            else return tail;\n        \n        } \n        // m > l\n        else {\n            // r > m > l\n            if (r > m) return mid;\n            // m > l > r\n            else if (l > r) return head;\n            // m > r > l\n            else return tail;\n        }\n    }\n    \n```\nStable recursive quick sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        List<Integer> l = new ArrayList<>();\n        for (int i : nums) {\n            l.add(i);\n        }\n        List<Integer> res = this.quickSort(l);\n        int size = nums.length;\n        for (int i = 0; i < size; ++i) {\n            nums[i] = res.get(i);\n        }\n        return nums;\n    }\n    public static List<Integer> quickSort(List<Integer> ar) {\n        // Base case\n        if(ar.size() <= 1) {\n            return ar;\n        }\n        // Let us choose middle element a pivot            \n        int mid = ar.size() / 2;\n        int pivat = ar.get(mid);\n             \n        // key element is used to break the array\n        // into 2 halves according to their values\n        List<Integer> smaller = new ArrayList<>();\n        List<Integer> greater = new ArrayList<>();\n             \n        // Put greater elements in greater list,\n        // smaller elements in smaller list. Also,\n        // compare positions to decide where to put.        \n        for (int ind = 0; ind < ar.size(); ind++) {\n            int val = ar.get(ind);\n            if ( ind != mid ) {\n                if ( val < pivat ) {\n                    smaller.add(val);\n                } else if (val > pivat) {\n                    greater.add(val);\n                } else {\n                    // If value is same, then considering\n                    // position to decide the list.                   \n                    if(ind < mid) {\n                        smaller.add(val);\n                    } else {\n                        greater.add(val);\n                    }\n                }\n            }\n        }\n        List<Integer> ans = new ArrayList<Integer>();              \n        List<Integer> sa1 = quickSort(smaller);\n        List<Integer> sa2 = quickSort(greater);\n        // add all elements of smaller list into ans list\n        for (Integer val1 : sa1) {\n            ans.add(val1);\n        }     \n        // add pivat element into ans list   \n        ans.add(pivat);\n        // add all elements of greater list into ans list\n        for(Integer val2 : sa2) {\n            ans.add(val2);\n        }\n        // return ans list\n        return ans;        \n    }\n}\n```\n\n\n3 ways quick sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        this.quick3(nums, 0, nums.length - 1);\n        return nums;\n    }\n    \n    private void quick3(int[] nums, int start, int end) {\n        if (start >= end) {\n            return;\n        }\n        \n        // choose the mid point as the pivot\n        int m = this.pickMediumIndex(nums, start, end, (start + (end - start)) / 2);\n        int pivot = nums[m];\n        \n        int temp = nums[start];\n        nums[start] = nums[m];\n        nums[m] = temp;\n        \n        int l = start;\n        int r = end;\n        int i = l + 1;\n        // start the process;\n        while (i <= r) {\n            // if less, move to front\n            if (nums[i] < pivot) {\n                int tmp = nums[i];\n                nums[i] = nums[l];\n                nums[l] = tmp;\n                ++i;\n                ++l;\n            }\n            // if equal, just keep the same position and move to next index.\n            else if (nums[i] == pivot) {\n                ++i;\n            } \n            // if greater, move to end;\n            // we do not increment i here because we do not know if the new element in ith position is greater or less than pivot.\n            else {\n                int tmp = nums[i];\n                nums[i] = nums[r];\n                nums[r] = tmp;\n                --r;\n            }\n        }\n        this.quick3(nums, start, l-1);\n        this.quick3(nums, r + 1, end);\n    }\n    \n    private int pickMediumIndex(int[] nums, int head, int tail, int mid) {\n        int l = nums[head];\n        int m = nums[mid];\n        int r = nums[tail];\n        if (l > m) {\n            // l > m > r\n            if (m > r) return mid;\n            // r > l > m\n            else if (r > l) return head;\n            //l > r > m\n            else return tail;\n        \n        } \n        // m > l\n        else {\n            // r > m > l\n            if (r > m) return mid;\n            // m > l > r\n            else if (l > r) return head;\n            // m > r > l\n            else return tail;\n        }\n    }\n}\n```\n\nIterative merge sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort2(nums);\n        return nums;\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) {\n                tmp[k] = nums[j];\n                ++k;\n                ++j;\n            } else if (j > r) {\n                tmp[k] = nums[i];\n                ++k;\n                ++i;\n            } else if (nums[i] > nums[j]) {\n                tmp[k] = nums[j];\n                ++k;\n                ++j;\n            } else {\n                tmp[k] = nums[i];\n                ++k;\n                ++i;\n            }\n        }\n        for (i = l; i <= r; ++i) {\n            nums[i] = tmp[i-l];\n        }\n    }\n}\n```\n\nRecursive merge sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return mergeSort(nums);\n        \n    }\n    \n    private int[] mergeSort(int[] nums) {\n        if (nums.length <= 1) return nums;\n        int length = nums.length;\n        int mid = nums.length / 2;\n        int[] left = new int[mid];\n        for (int i = 0; i < mid; ++i) {\n            left[i] = nums[i];\n        }\n        int[] right = new int[nums.length - mid];\n        for (int i = mid; i < length; ++i) {\n            right[i - mid] = nums[i];\n        }\n        left = mergeSort(left);\n        right = mergeSort(right);\n        return merge(left, right);\n    }\n    private int[] merge(int[] l, int[] r) {\n        int[] res = new int[l.length+r.length];\n        int lLen = l.length;\n        int rLen = r.length;\n        int i = 0;\n        int li = 0;\n        int ri = 0;\n        while (lLen > 0 && rLen > 0) {\n            if (l[li] <= r[ri]) {\n                res[i] = l[li];\n                ++i;\n                li++;\n                --lLen;\n            } else {\n                res[i] = r[ri];\n                ++i;\n                ri++;\n                --rLen;\n            }\n        }\n        while (lLen > 0) {\n            res[i] = l[li];\n            --lLen;\n            ++i;\n            ++li;\n        }\n        while (rLen > 0) {\n            res[i] = r[ri];\n            --rLen;\n            ++i;\n            ++ri;\n        }\n        return res;\n    }\n}\n```\n\nMax Heap Sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return maxHeapSort(nums);\n    }\n    \n    private int[] maxHeapSort(int[] nums) {\n        int[] res = new int[nums.length];\n        int size = nums.length;\n        // build heap. start from first half because the second half is children.\n        for (int i = size / 2 - 1; i >= 0; --i) {\n            this.maxHeapify(nums, size, i);\n        }\n        for (int i = size - 1; i >= 0; --i) {\n            // put current node to the end;\n            int temp = nums[0];\n            nums[0] = nums[i];\n            nums[i] = temp;\n            // put current largest into ith position.\n            this.maxHeapify(nums, i, 0);\n        }\n        return nums;\n    }\n    \n    private void maxHeapify(int[] nums, int size, int i) {\n        int largest = i; \n        int left = 2*i + 1;\n        int right = 2*i + 2;\n        if (left < size) {\n            if (nums[left] > nums[largest]) largest = left;\n        }\n        if (right < size) {\n            if (nums[right] > nums[largest]) largest = right;\n        }\n        if (largest != i) {\n            int temp = nums[i];\n            nums[i] = nums[largest];\n            nums[largest] = temp;\n            this.maxHeapify(nums, size, largest);\n        }\n    }\n}\n```\n\nMin Heap Sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        this.heapSort(nums, nums.length);\n        return nums;\n    }\n    \n    // main function to do heap sort\n    static void heapSort(int arr[], int n)\n    {\n        // Build heap (rearrange array)\n        for (int i = n / 2 - 1; i >= 0; i--)\n            heapify(arr, n, i);\n \n        // One by one extract an element from heap\n        for (int i = n - 1; i >= 0; i--) {\n             \n            // Move current root to end\n            int temp = arr[0];\n            arr[0] = arr[i];\n            arr[i] = temp;\n \n            // call max heapify on the reduced heap\n            heapify(arr, i, 0);\n        }\n        int l = 0;\n        int r = n - 1;\n        while (l < r) {\n            int temp = arr[l];\n            arr[l] = arr[r];\n            arr[r] = temp;\n            ++l;\n            --r;\n        }\n    }\n    \n    static void heapify(int arr[], int n, int i)\n    {\n        int smallest = i; // Initialize smalles as root\n        int l = 2 * i + 1; // left = 2*i + 1\n        int r = 2 * i + 2; // right = 2*i + 2\n \n        // If left child is smaller than root\n        if (l < n && arr[l] < arr[smallest])\n            smallest = l;\n \n        // If right child is smaller than smallest so far\n        if (r < n && arr[r] < arr[smallest])\n            smallest = r;\n \n        // If smallest is not root\n        if (smallest != i) {\n            int temp = arr[i];\n            arr[i] = arr[smallest];\n            arr[smallest] = temp;\n \n            // Recursively heapify the affected sub-tree\n            heapify(arr, n, smallest);\n        }\n    }\n}\n```\n\n3 way merge sort\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        return this.merge3ways(nums);\n    }\n    \n    private int[] merge3ways(int[] nums) {\n        if (nums == null) {\n            return nums;\n        }\n        \n        int length = nums.length;\n        int[] tar = new int[length];\n        for (int i = 0; i < length; ++i) {\n            tar[i] = nums[i];\n        }\n        this.mergeSort(nums, 0, length, tar);\n        return nums;\n    }\n    \n    private void mergeSort(int[] ori, int l, int h, int[] tar) {\n        if (h - l < 2) {\n            return;\n        }\n        int m1 = l + ((h - l) / 3);\n        int m2 = l + 2 * ((h - l) / 3) + 1;\n        this.mergeSort(tar, l, m1, ori);\n        this.mergeSort(tar, m1, m2, ori);\n        this.mergeSort(tar, m2, h, ori);\n        this.merge(tar, l, m1, m2, h, ori);\n    }\n    \n    private void merge(int[] ori, int low, int m1, int m2, int h, int[] tar) {\n        int i = low;\n        int j = m1;\n        int k = m2;\n        int l = low;\n        while ( (i < m1) && (j < m2) && (k < h)) {\n            if (ori[i] < ori[j]) {\n                if (ori[i] < ori[k]) {\n                    tar[l++] = ori[i++];\n                } else {\n                    tar[l++] = ori[k++];\n                }\n            } else {\n                if (ori[j] < ori[k]) {\n                    tar[l++] = ori[j++];\n                } else {\n                    tar[l++] = ori[k++];\n                }\n            }\n        }\n        \n        while ( (i < m1) && (j < m2)) {\n            if (ori[i] < ori[j]) {\n                tar[l++] = ori[i++];\n            } else {\n                tar[l++] = ori[j++];\n            }\n        }\n        \n        while ((j < m2) && (k < h)) {\n            if (ori[j] < ori[k]) {\n                tar[l++] = ori[j++];\n            } else {\n                tar[l++] = ori[k++];\n            }\n        }\n        \n        while ( (i < m1) && (k < h)) {\n            if (ori[i] < ori[k]) {\n                tar[l++] = ori[i++];\n            } else {\n                tar[l++] = ori[k++];\n            }\n        }\n        \n        while (i < m1) {\n            tar[l++] = ori[i++];\n        }\n        \n        while (j < m2) {\n            tar[l++] = ori[j++];\n        }\n        \n        while (k < h) {\n            tar[l++] = ori[k++];\n        }\n    }\n}\n```
['Recursion', 'Sorting', 'Heap (Priority Queue)', 'Merge Sort', 'Iterator', 'Java']