Java Solution|| Explained || 3 Methods || Hybrid sorting - Insertion, Quick & Merge sort || Fast
Explanation:\n OOH the question is asking us to sort an array, so simple right? use Arrays.sort(nums) and be  done with life, but stop let\'s try not to be lazy
**Explanation:**\n* OOH the question is asking us to sort an array, so simple right? use Arrays.sort(nums) and be  done with life, but stop let\'s try not to be lazy today? we are going to solve this using top three basic sorting algorithms -- Insertion sort, Quick sort and Merge sort depending on the size of array.\n1.  *Insertion sort* - stable sort and in-place, T: O(N^2) and S: O(1), good for lower size arrays.\n2. *Quick sort* - unstable and in-place, T: O(Nlogn) - average case and S: O(1) (ignorign recursion call stack memory), divide and conquer algorithm. The key part is partioning(Naive, Lomuto and Hoare\'s partition algorithm).\n3. *Merge Sort* - stable sort and not in-place(arguable) , T: O(NlogN) S: O(N) , used in external sorting - for massive data. The key part is mergeFunction - I used two pointer approach.\n\n**Code:**\n\n       public int[] sortArray(int[] nums) {\n\t// we can check if our array is sorted or not by O(N) time.\n        if (nums.length < 25) {\n            insertionSort(nums);\n        } else if (nums.length > 25 && nums.length < 1000 ) {\n           quickSort(nums, 0, nums.length - 1);\n        } else {\n\t\t    mergeSort(nums, 0, nums.length - 1);\n        }\n        return nums;\n    }\n     static void mergeFun(int[] arr, int l, int m, int r) {\n        int n1 = m + 1 - l;\n        int n2 = r - m;\n        int[] left = new int[n1];\n        for (int i = 0; i < n1; i++) {\n            left[i] = arr[l + i];\n        }\n        int[] right = new int[n2];\n        for (int i = 0; i < n2; i++) {\n            right[i] = arr[m + 1 + i];\n        }\n        int i = 0, j = 0, k = l;\n        while (i < n1 || j < n2) {\n            if (j == n2 || i < n1 && left[i] < right[j])\n                arr[k++] = left[i++];\n            else\n                arr[k++] = right[j++];\n        }\n    }\n\n    static void mergeSort(int[] arr, int low, int high) {\n        if (low < high) {\n            int middle = (high - low) / 2 + low;\n            mergeSort(arr, low, middle);\n            mergeSort(arr, middle + 1, high);\n            mergeFun(arr, low, middle, high);\n        }\n    }\n\n    static int partitionUsingHoare(int[] arr, int l, int h) {\n        int pivot = arr[l];\n        int i = l - 1;\n        int j = h + 1;\n        while (true) {\n            do {\n                i++;\n            } while (arr[i] < pivot);\n            do {\n                j--;\n            } while (arr[j] > pivot);\n            if (i >= j) return j;\n            swap(arr, i, j);\n        }\n    }\n\n    static void swap(int[] arr, int i, int j) {\n        int temp = arr[i];\n        arr[i] = arr[j];\n        arr[j] = temp;\n    }\n\n    static void quickSort(int[] arr, int low, int high) {\n        if (low < high) {\n            int p = partitionUsingHoare(arr, low, high);\n            quickSort(arr, low, p);\n            quickSort(arr, p + 1, high);\n        }\n    }\n\n    static void insertionSort(int[] nums) { \n        for (int i = 0; i < nums.length; i++) {\n            int key = nums[i];\n            int j = i - 1;\n            while (j >= 0 && nums[j] > key) {\n                nums[j + 1] = nums[j];\n                j--;\n            }\n            nums[j + 1] = key;\n        }\n    }\n\n\n**IMP**: You can also bookmark/ subscribe to this post so as to revise above Sorting Algorithms whenvever you need to.\n\n**NOTE:**\nIf you find this post helpful then *please upvote*. It keeps me motivated to post such helpful solutions. Thanks!
['Sorting', 'Merge Sort', 'Java']