Explanation which makes the concept clear to interpret... Beats 98.75%
no misunderstandings please legal upvotes from my peers..\n\n# Approach\nThe main function sortArray contains a nested function quick_sort, which is a common pa
## no misunderstandings please legal upvotes from my peers..\n\n# Approach\nThe main function sortArray contains a nested function quick_sort, which is a common pattern to encapsulate the recursive logic within the sorting function and allows us to use variables from the outer scope.\n\nquick_sort takes two arguments, l and r, which are the indices of the left and right boundaries of the sub-array that it needs to sort.\n\nThe termination condition for the recursion is when the left boundary l is greater than or equal to the right boundary r. At this point, the sub-array has zero or one element and is considered sorted.\n\nA pivot element x is chosen using randint(l, r) to randomly select an index between l and r, inclusive. The random pivot mitigates the risk of encountering the worst-case time complexity.\n\nThree pointers are established: i is initially set to one less than the left boundary l, j is one more than the right boundary r, and k is set to the left boundary l.\n\nAn iterative process starts where the k pointer moves from l to j. During this process:\n\nIf the current element nums[k] is less than the pivot x, it is swapped with the element at i+1, and both i and k are incremented. This effectively moves the current element to the left partition (elements less than the pivot).\nIf nums[k] is greater than the pivot x, the current element is swapped with the element just before j, and j is decreased. This moves the current element to the right partition (elements greater than the pivot).\nIf nums[k] is equal to the pivot x, only k is incremented since the element at k is already equal to the pivot, and we want to keep this partition in the middle.\nThe array now has three partitions: elements less than the pivot (l to i), elements equal to the pivot (i+1 to j-1), and elements greater than the pivot (j to r). The elements equal to the pivot are already at their final destination.\n\nRecursive calls are made to quick_sort for the left partition (l to i) and the right partition (j to r). Note that the elements equal to the pivot are not included.\n\nOnce all recursive calls are completed, the entire array has been sorted in place, and the sorted array nums is returned.\n\nData Structures Used:\n\nThe primary data structure is the input array nums. No additional data structure is utilized, which contributes to the algorithm\'s small space complexity.\n\n# Code\n\n```python3 []\nfrom random import randint\nfrom typing import List\n\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        # Helper function to perform quick sort.\n        def quick_sort(left, right):\n            # Base case: If the current segment is empty or has only one element, no need to sort.\n            if left >= right:\n                return\n          \n            # Choose a random pivot element from the segment.\n            pivot = nums[randint(left, right)]\n            # Initialize pointers: \n            # \'less_than_pointer\' marks the end of the segment with elements less than pivot.\n            # \'greater_than_pointer\' marks the start of the segment with elements greater than pivot.\n            # \'current\' is used to scan through the list. \n            less_than_pointer, greater_than_pointer, current = left - 1, right + 1, left\n          \n            # Iterate until \'current\' is less than \'greater_than_pointer\'.\n            while current < greater_than_pointer:\n                if nums[current] < pivot:\n                    # Move the element to the segment with elements less than pivot.\n                    less_than_pointer += 1\n                    nums[less_than_pointer], nums[current] = nums[current], nums[less_than_pointer]\n                    current += 1\n                elif nums[current] > pivot:\n                    # Move the element to the segment with elements greater than pivot.\n                    greater_than_pointer -= 1\n                    nums[greater_than_pointer], nums[current] = nums[current], nums[greater_than_pointer]\n                else:\n                    # If the current element is equal to the pivot, move to the next element.\n                    current += 1\n\n            # Recursively apply quick sort to the segment with elements less than pivot.\n            quick_sort(left, less_than_pointer)\n            # Recursively apply quick sort to the segment with elements greater than pivot.\n            quick_sort(greater_than_pointer, right)\n\n        # Call the quick_sort function with the initial boundaries of the list.\n        quick_sort(0, len(nums) - 1)\n        # Return the sorted list.\n        return nums\n```\n```javascript []\n// This function sorts an array of numbers using Quick Sort algorithm.\nfunction sortArray(nums: number[]): number[] {\n    // Helper function to perform the quickSort algorithm.\n    function quickSort(left: number, right: number) {\n        // If the current segment is empty or has one element, no sorting is needed.\n        if (left >= right) {\n            return;\n        }\n\n        let i = left - 1;\n        let j = right + 1;\n\n        // Choose the pivot element from the middle of the segment.\n        const pivot = nums[(left + right) >> 1];\n\n        // Partition process: elements < pivot go to the left, elements > pivot go to the right.\n        while (i < j) {\n            // Find left element greater than or equal to the pivot.\n            while (nums[++i] < pivot);\n            // Find right element less than or equal to the pivot.\n            while (nums[--j] > pivot);\n\n            // If pointers have not crossed, swap the elements.\n            if (i < j) {\n                [nums[i], nums[j]] = [nums[j], nums[i]];\n            }\n        }\n\n        // Recursively apply the same logic to the left partition.\n        quickSort(left, j);\n        // Recursively apply the same logic to the right partition.\n        quickSort(j + 1, right);\n    }\n\n    // Obtain the length of the array to sort.\n    const n = nums.length;\n    // Call the quickSort helper function on the entire array.\n    quickSort(0, n - 1);\n\n    // Return the sorted array.\n    return nums;\n}\n\n```\n\n```C++ []\n#include <vector>\n#include <functional> // For std::function\n\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        // A lambda function for recursive quick sort\n        std::function<void(int, int)> quickSort = [&](int left, int right) {\n            // Base case: If the current segment is empty or a single element, no need to sort\n            if (left >= right) {\n                return;\n            }\n\n            // Initialize pointers for partitioning process\n            int pivotIndex = left + (right - left) / 2; // Choose middle element as pivot\n            int pivotValue = nums[pivotIndex];\n            int i = left - 1;\n            int j = right + 1;\n          \n            // Partition the array into two halves\n            while (i < j) {\n                // Increment i until nums[i] is greater or equal to pivot\n                do {\n                    i++;\n                } while (nums[i] < pivotValue);\n\n                // Decrement j until nums[j] is less or equal to pivot\n                do {\n                    j--;\n                } while (nums[j] > pivotValue);\n\n                // If i and j haven\'t crossed each other, swap the elements\n                if (i < j) {\n                    std::swap(nums[i], nums[j]);\n                }\n            }\n\n            // Recursively apply the same logic to the left and right halves of the array\n            quickSort(left, j);     // Apply quicksort to the left subarray\n            quickSort(j + 1, right); // Apply quicksort to the right subarray\n        };\n\n        // Start the quick sort from the first to the last element\n        quickSort(0, nums.size() - 1);\n\n        // Return the sorted array\n        return nums;\n    }\n};\n\n```\n\n
['Python', 'C++', 'Python3', 'JavaScript']