Skip to content

912. Sort an Array 👍

Approach 1: Merge Sort

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
    return nums;
  }

 private:
  void mergeSort(vector<int>& nums, int l, int r) {
    if (l >= r)
      return;
    const int m = (l + r) / 2;
    mergeSort(nums, l, m);
    mergeSort(nums, m + 1, r);
    merge(nums, l, m, r);
  }

  void merge(vector<int>& nums, 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 (nums[i] < nums[j])
        sorted[k++] = nums[i++];
      else
        sorted[k++] = nums[j++];

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

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

    copy(sorted.begin(), sorted.end(), nums.begin() + l);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
  }

  private void mergeSort(int[] nums, int l, int r) {
    if (l >= r)
      return;
    final int m = (l + r) / 2;
    mergeSort(nums, l, m);
    mergeSort(nums, m + 1, r);
    merge(nums, l, m, r);
  }

  private void merge(int[] nums, 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 (nums[i] < nums[j])
        sorted[k++] = nums[i++];
      else
        sorted[k++] = nums[j++];

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
  def sortArray(self, nums: list[int]) -> list[int]:
    self._mergeSort(nums, 0, len(nums) - 1)
    return nums

  def _mergeSort(self, nums: list[int], l: int, r: int) -> None:
    if l >= r:
      return

    def merge(nums: 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 nums[i] < nums[j]:
          sorted[k] = nums[i]
          k += 1
          i += 1
        else:
          sorted[k] = nums[j]
          k += 1
          j += 1

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

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

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

    m = (l + r) // 2
    self._mergeSort(nums, l, m)
    self._mergeSort(nums, m + 1, r)
    merge(nums, l, m, r)

Approach 2: Heap Sort

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    heapSort(nums);
    return nums;
  }

 private:
  void heapSort(vector<int>& nums) {
    buildMaxHeap(nums);
    int heapSize = nums.size();
    for (int i = nums.size() - 1; i > 0; --i) {
      swap(nums[i], nums[0]);
      --heapSize;
      maxHeapify(nums, 0, heapSize);
    }
  }

  void buildMaxHeap(vector<int>& nums) {
    for (int i = nums.size() / 2; i >= 0; --i)
      maxHeapify(nums, i, nums.size());
  }

  void maxHeapify(vector<int>& nums, int i, int heapSize) {
    const int l = 2 * i + 1;
    const int r = 2 * i + 2;
    int largest = i;
    if (l < heapSize && nums[largest] < nums[l])
      largest = l;
    if (r < heapSize && nums[largest] < nums[r])
      largest = r;
    if (largest != i) {
      swap(nums[largest], nums[i]);
      maxHeapify(nums, largest, heapSize);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
  public int[] sortArray(int[] nums) {
    heapSort(nums);
    return nums;
  }

  private void heapSort(int[] nums) {
    buildMaxHeap(nums);
    int heapSize = nums.length;
    for (int i = nums.length - 1; i > 0; --i) {
      swap(nums, i, 0);
      --heapSize;
      maxHeapify(nums, 0, heapSize);
    }
  }

  private void buildMaxHeap(int[] nums) {
    for (int i = nums.length / 2; i >= 0; --i)
      maxHeapify(nums, i, nums.length);
  }

  private void maxHeapify(int[] nums, int i, int heapSize) {
    final int l = 2 * i + 1;
    final int r = 2 * i + 2;
    int largest = i;
    if (l < heapSize && nums[largest] < nums[l])
      largest = l;
    if (r < heapSize && nums[largest] < nums[r])
      largest = r;
    if (largest != i) {
      swap(nums, largest, i);
      maxHeapify(nums, largest, heapSize);
    }
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def sortArray(self, nums: list[int]) -> list[int]:
    self._heapSort(nums)
    return nums

  def _heapSort(self, nums: list[int]) -> None:
    def maxHeapify(nums: list[int], i: int, heapSize: int) -> None:
      l = 2 * i + 1
      r = 2 * i + 2
      largest = i
      if l < heapSize and nums[largest] < nums[l]:
        largest = l
      if r < heapSize and nums[largest] < nums[r]:
        largest = r
      if largest != i:
        nums[largest], nums[i] = nums[i], nums[largest]
        maxHeapify(nums, largest, heapSize)

    def buildMaxHeap(nums: list[int]) -> None:
      for i in range(len(nums) // 2, -1, -1):
        maxHeapify(nums, i, len(nums))

    buildMaxHeap(nums)
    heapSize = len(nums)
    for i in reversed(range(1, len(nums))):
      nums[i], nums[0] = nums[0], nums[i]
      heapSize -= 1
      maxHeapify(nums, 0, heapSize)

Approach 3: Quick Sort

  • Time: $O(n\log n) \to O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1);
    return nums;
  }

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

    const int m = partition(nums, l, r);
    quickSort(nums, l, m - 1);
    quickSort(nums, m + 1, r);
  }

  int partition(vector<int>& nums, int l, int r) {
    const int randIndex = rand() % (r - l + 1) + l;
    swap(nums[randIndex], nums[r]);
    const int pivot = nums[r];
    int nextSwapped = l;
    for (int i = l; i < r; ++i)
      if (nums[i] <= pivot)
        swap(nums[nextSwapped++], nums[i]);
    swap(nums[nextSwapped], nums[r]);
    return nextSwapped;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  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;

    final int m = partition(nums, l, r);
    quickSort(nums, l, m - 1);
    quickSort(nums, m + 1, r);
  }

  private int partition(int[] nums, int l, int r) {
    final int randIndex = new Random().nextInt(r - l + 1) + l;
    swap(nums, randIndex, r);
    final int pivot = nums[r];
    int nextSwapped = l;
    for (int i = l; i < r; ++i)
      if (nums[i] <= pivot)
        swap(nums, nextSwapped++, i);
    swap(nums, nextSwapped, r);
    return nextSwapped;
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def sortArray(self, nums: list[int]) -> list[int]:
    self._quickSort(nums, 0, len(nums) - 1)
    return nums

  def _quickSort(self, nums: list[int], l: int, r: int) -> None:
    if l >= r:
      return

    def partition(nums: list[int], l: int, r: int) -> int:
      randIndex = random.randint(0, r - l) + l
      nums[randIndex], nums[r] = nums[r], nums[randIndex]
      pivot = nums[r]
      nextSwapped = l
      for i in range(l, r):
        if nums[i] <= pivot:
          nums[nextSwapped], nums[i] = nums[i], nums[nextSwapped]
          nextSwapped += 1
      nums[nextSwapped], nums[r] = nums[r], nums[nextSwapped]
      return nextSwapped

    m = partition(nums, l, r)
    self._quickSort(nums, l, m - 1)
    self._quickSort(nums, m + 1, r)