LeetCode Solutions

			

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
    return nums;
  }

 private:
  void mergeSort(vector<int>& A, int l, int r) {
    if (l >= r)
      return;

    const int m = (l + r) / 2;
    mergeSort(A, l, m);
    mergeSort(A, m + 1, r);
    merge(A, l, m, r);
  }

  void merge(vector<int>& A, int l, int m, int r) {
    vector<int> sorted(r - l + 1);
    int k = 0;      // sorted's index
    int i = l;      // left's index
    int j = m + 1;  // right's index

    while (i <= m && j <= r)
      if (A[i] < A[j])
        sorted[k++] = A[i++];
      else
        sorted[k++] = A[j++];

    // Put possible remaining left part to the sorted array
    while (i <= m)
      sorted[k++] = A[i++];

    // Put possible remaining right part to the sorted array
    while (j <= r)
      sorted[k++] = A[j++];

    copy(begin(sorted), end(sorted), begin(A) + l);
  }
};

			

class Solution {
  public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
  }

  private void mergeSort(int[] A, int l, int r) {
    if (l >= r)
      return;

    final int m = (l + r) / 2;
    mergeSort(A, l, m);
    mergeSort(A, m + 1, r);
    merge(A, l, m, r);
  }

  private void merge(int[] A, int l, int m, int r) {
    int[] sorted = new int[r - l + 1];
    int k = 0;     // sorted's index
    int i = l;     // left's index
    int j = m + 1; // right's index

    while (i <= m && j <= r)
      if (A[i] < A[j])
        sorted[k++] = A[i++];
      else
        sorted[k++] = A[j++];

    // Put possible remaining left part to the sorted array
    while (i <= m)
      sorted[k++] = A[i++];

    // Put possible remaining right part to the sorted array
    while (j <= r)
      sorted[k++] = A[j++];

    System.arraycopy(sorted, 0, A, l, sorted.length);
  }
}

			

class Solution:
  def sortArray(self, nums: List[int]) -> List[int]:
    def mergeSort(A: List[int], l: int, r: int) -> None:
      if l >= r:
        return

      def merge(A: List[int], l: int, m: int, r: int) -> None:
        sorted = [0] * (r - l + 1)
        k = 0  # sorted's index
        i = l  # left's index
        j = m + 1  # right's index

        while i <= m and j <= r:
          if A[i] < A[j]:
            sorted[k] = A[i]
            k += 1
            i += 1
          else:
            sorted[k] = A[j]
            k += 1
            j += 1

        # Put possible remaining left part to the sorted array
        while i <= m:
          sorted[k] = A[i]
          k += 1
          i += 1

        # Put possible remaining right part to the sorted array
        while j <= r:
          sorted[k] = A[j]
          k += 1
          j += 1

        A[l:l + len(sorted)] = sorted

      m = (l + r) // 2
      mergeSort(A, l, m)
      mergeSort(A, m + 1, r)
      merge(A, l, m, r)

    mergeSort(nums, 0, len(nums) - 1)
    return nums