Using QuickSort(median as a pivot) which works and mergeSort!!
Intuition\n Describe your first thoughts on how to solve this problem. \nSince this problem requires O(nlog\u2061n) time complexity, two sorting techniques that
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince this problem requires O(nlog\u2061n) time complexity, two sorting techniques that comes to our mind at first is merge and quick sort (without using any built-in functions).\nThe plan wasn\'t to write this post and on that account this is my first such post on LinkedIn but after going through lot of solutions and discussions, I thought my post will make some contribution. \nI saw a lot of folks having doubts like why isn\'t quick sort working on this problem statement? Few months back Quick Sort was working really fine why not now?\nWell, to answer this and showing my approach I am writing this post! However Quick Sort isn\'t the most optimal one, so if you\'re looking for an optimal approach then it isn\'t for you.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nApproach is really simple, plain quicksort and merge sort! However the trick is in the partition function. \n### Quick Sort \nQuick Sort uses a Divide and Conquer approach, We can choose the pivot element. The key process in quicksort is partition(). The target of partition function is to place the pivot element properly, as to the smaller elements than pivot are to the left and greater elements to the right of the pivot. \n\n\nPartition in Quick Sort can be done in multiple ways :\n    - Always pick the first element as a pivot.\n    - Always pick the last element as a pivot \n    - Pick a random element as a pivot.\n    - Pick the middle as the pivot.\n\nIn my first approach I was picking the starting element as the pivot element\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        //without using built-in fn in nlogn time complexity -> quick   \n        //sort\n        quickSort(nums,0,nums.length-1);\n        return nums;\n    }\n    private void quickSort(int[] a, int lb , int ub){\n        if (lb<ub){\n            int loc = partition(a, lb,ub);\n            quickSort(a, lb,loc-1);\n            quickSort(a, loc+1,ub);\n        }\n    }\n    private int partition(int[] a, int lb, int ub){\n        int pivot = a[lb];\n        int start=lb;\n        int end = ub;\n        while(start<end){\n            while(start<=end && a[start]<=pivot){\n                start++; \n            }\n            while(start<=end && a[end]>pivot){\n                end--;\n            }\n            if(start<end){\n                swap(a, start, end);\n            }\n        }\n        swap(a, lb, end);\n        return end;\n    }\n    private void swap(int[]a , int i, int j){\n        int temp = a[i];\n        a[i]=a[j];\n        a[j]=temp;\n    }\n}\n\n```\nBut this approach was giving TLE (Time Limit Exceeded). Why is it so?\nThe time complexity of Quick Sort is generally O(nlog\u2061n) , but this can degrade to O(n^2) in the worst-case scenarios, depending on how the pivot is chosen. \nWorst Case:\nThe Worst case in this problem is the array is nearly sorted and if we choose start or end element as the pivot element complexity could go to O(n^2) as it can lead to unbalanced partition which can result to one subarray of n-1 size and another of 0. To avoid this , we can simply choose the median or randomized partition which reduces the chances of worst case scenario. In my second approach I have chosen the median(middle) element to be the partition which tends to create more balanced partition which reduces the probability of worst case scenario.\n\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        quickSort(nums, 0, nums.length - 1);\n        return nums;\n    }\n\n    private void quickSort(int[] a, int lb, int ub) {\n        if (lb < ub) {\n            int loc = partition(a, lb, ub);\n            quickSort(a, lb, loc - 1);\n            quickSort(a, loc + 1, ub);\n        }\n    }\n\n    private int partition(int[] a, int lb, int ub) {\n        int mid = lb + (ub - lb) / 2;\n        swap(a, mid, lb); \n        int pivot = a[lb]; \n        int start = lb;\n        int end = ub;\n\n        while (start < end) {\n            while (start <= end && a[start] <= pivot) {\n                start++;\n            }\n            while (start <= end && a[end] > pivot) {\n                end--;\n            }\n            if (start < end) {\n                swap(a, start, end);\n            }\n        }\n        swap(a, lb, end);\n        return end;\n    }\n\n    private void swap(int[] a, int i, int j) {\n        int temp = a[i];\n        a[i] = a[j];\n        a[j] = temp;\n    }\n}\n\n```\nBetter approach will be simple merge sort which again uses divide and conquer approach and is safe with O(nlogn)\nwhich is mentioned below\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(nlogn)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(logn)\n    O(n) // for merge sort\n\n# Code\n```\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        mergeSort(nums, 0, nums.length - 1);\n        return nums;\n    }\n\n    private static void mergeSort(int[] A, int lb, int ub) {\n        if (lb < ub) {\n            int mid = (lb + ub) / 2;\n            mergeSort(A, lb, mid);\n            mergeSort(A, mid + 1, ub);\n            merge(A, lb, mid, ub);\n        }\n    }\n\n    private static void merge(int[] A, int lb, int mid, int ub) {\n        int i = lb;\n        int j = mid + 1;\n        int k = 0; \n        int[] b = new int[ub - lb + 1];\n\n        while (i <= mid && j <= ub) {\n            if (A[i] <= A[j]) {\n                b[k++] = A[i++];\n            } else {\n                b[k++] = A[j++];\n            }\n        }\n\n        while (i <= mid) {\n            b[k++] = A[i++];\n        }\n        while (j <= ub) {\n            b[k++] = A[j++];\n        }\n        for (i = 0; i < b.length; i++) {\n            A[lb + i] = b[i];\n        }\n    }\n}\n\n```\nPlease do upvote my post!
['Java']