Quick Sort with explanantion
Pick the middle number as the pivot.\n2. Set two poiners, left and right, on the start index and end index.\n3. left pointer searches for next number that is bi
1. Pick the middle number as the pivot.\n2. Set two poiners, left and right, on the start index and end index.\n3. left pointer searches for next number that is bigger or equal to pivot.\n4. right pointer searches for next number that is smaller or equal to pivot.\n5. if there exists two numbers as described, swap them. \n**6. So on the left part of the left pointer, all numbers are smaller or equal to pivot. For the right part of right pointer, all numbers are bigger or equal to pivot.**\n7. keep traversing until left pointer > right pointer, which means all numbers have been visited and set to correct positions.\n8. divide into [start, right], [left, end], quick sort the subarray respectively.\n   \n```\n   public int[] sortArray(int[] nums) {\n        if (nums == null || nums.length == 0) {\n            return nums;\n        }\n        \n        quickSort(nums, 0, nums.length - 1);\n        return nums;\n    }\n    \n    private void quickSort(int[] nums, int start, int end) {\n        if (start >= end) return;\n        \n        int left = start, right = end;\n\t\t// Ideally, numbers are approximately increasing, which means the middle number is most likey the median number. \n\t\t// The closer pivot is to the median number, the less swapping and recursion we need to do.\n        int pivot = nums[left + (right - left) / 2];\n        // with (left <= right), we can end with: \n\t\t// 1. x, x, x, right, left, x, x, x,\n\t\t// or\n\t\t// 2. x, x, x, right, pivot, left, x, x, x\n\t\t// easy to divide without boundary issues\n        while (left <= right) {\n\t\t\t// if we put nums[left] <= pivot, for array like [2, 1], 1 swap with itself and leads to dead loop\n            while (left <= right && nums[left] < pivot) left++;\n            while (left <= right && nums[right] > pivot) right--;\n            if (left <= right) {\n                int temp = nums[left];\n                nums[left] = nums[right];\n                nums[right] = temp;\n                left++;\n                right--;\n            }\n        }\n        \n        quickSort(nums, start, right);\n        quickSort(nums, left, end);\n    }\n```\n\ntime complexity: \non average O(nlogn); \narray can be divied **O(logn)** times, each time the whole array will be traversed, **O(n) time** every traversal . \nworst case O(n * n): \n[0, 0, 1, 0, 0], if we always choose smallest or biggest number as pivot, then **O(n)** times traverses with **O(n**) time every traversal.\n\t\t\t\t\t\t\t\nspace complexity: \non average O(logn), worst case O(n);\ndecided by the depth of recursion.
[]