912. Sort an Array.md

912. Sort an Array

---

Difficulty : Medium

Related Topics : Sort

---

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

• 1 <= nums.length <= 50000
• ``-50000 <= nums[i] <= 50000`

---

Solution

• mine
  • Java

    • Arrays.sort Runtime: 3 ms, faster than 99.34%, Memory Usage: 46.7 MB, less than 83.80% of Java online submissions

      // O(N*logN)time
      // O(1)space
      public int[] sortArray(int[] nums) {
          Arrays.sort(nums);
          return nums;
      }
      

    • Quick Sort Runtime: 8 ms, faster than 39.30%, Memory Usage: 54.2 MB, less than 12.08% of Java online submissions

      // O(N*logN)time
      // O(1)space
      public int[] sortArray(int[] nums) {
          quickSort(nums, 0, nums.length - 1);
          return nums;
      }
      
      private void quickSort(int[] nums, int l, int r) {
          if (l >= r) return;
          int mid = partition(nums, l, r);
          quickSort(nums, l, mid);
          quickSort(nums, mid + 1, r);
      }
      
      private int partition(int[] nums, int l, int r) {
          int pivot = nums[l];
          while (l < r) {
              while (l < r && nums[r] >= pivot) r--;
              nums[l] = nums[r];
              while (l < r && nums[l] <= pivot) l++;
              nums[r] = nums[l];
          }
          nums[l] = pivot;
          return l;
      }
      

    • DualPivotQuickSort Runtime: 3 ms, faster than 99.34%, Memory Usage: 47.3 MB, less than 53.83% of Java online submissions

      // O(N*logN)time
      // O(1)space
      public int[] sortArray(int[] nums) {
          dualPivotQuickSort(nums, 0, nums.length - 1);
          return nums;
      }
      
      void dualPivotQuickSort(int[] a, int start, int end) {
          if (start < end) {
              if (a[start] > a[end]) {
                  swapArray(a, start, end);
              }
              int p1 = a[start];
              int p2 = a[end];
              int i = start;
              int j = end;
              int k = start + 1;
              OUT_LOOP:
              while (k < j) {
                  if (a[k] < p1) {
                      i++;
                      swapArray(a, i, k);
                      k++;
                  } else if (a[k] <= p2) {
                      k++;
                  } else {
                      while (a[j] >= p2) {
                          j--;
                          if (j <= k) {
                              break OUT_LOOP;
                          }
                      }
                      if (a[j] < p1) {
                          swapArray(a, j, k);
                          i++;
                          swapArray(a, i, k);
                      } else {
                          swapArray(a, j, k);
                      }
                      k++;
                  }
              }
              swapArray(a, i, start);
              swapArray(a, j, end);
              dualPivotQuickSort(a, start, i - 1);
              dualPivotQuickSort(a, i + 1, j - 1);
              dualPivotQuickSort(a, j + 1, end);
          }
      }
      
      void swapArray(int[] A, int i, int j) {
          if (i == j) return;
          int t = A[i];
          A[i] = A[j];
          A[j] = t;
      }
      

---