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
41
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 the possible remaining left part into the sorted array.
    while (i <= m)
      sorted[k++] = A[i++];

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

    copy(sorted.begin(), sorted.end(), A.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
39
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 the possible remaining left part into the sorted array.
    while (i <= m)
      sorted[k++] = A[i++];

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

    System.arraycopy(sorted, 0, A, 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]:
    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 the possible remaining left part into the sorted array.
        while i <= m:
          sorted[k] = A[i]
          k += 1
          i += 1

        # Put the possible remaining right part into 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

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>& A) {
    buildMaxHeap(A);
    int heapSize = A.size();
    for (int i = A.size() - 1; i > 0; --i) {
      swap(A[i], A[0]);
      --heapSize;
      maxHeapify(A, 0, heapSize);
    }
  }

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

  void maxHeapify(vector<int>& A, int i, int heapSize) {
    const int l = 2 * i + 1;
    const int r = 2 * i + 2;
    int largest = i;
    if (l < heapSize && A[largest] < A[l])
      largest = l;
    if (r < heapSize && A[largest] < A[r])
      largest = r;
    if (largest != i) {
      swap(A[largest], A[i]);
      maxHeapify(A, 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[] A) {
    buildMaxHeap(A);
    int heapSize = A.length;
    for (int i = A.length - 1; i > 0; --i) {
      swap(A, i, 0);
      --heapSize;
      maxHeapify(A, 0, heapSize);
    }
  }

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

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

  private void swap(int[] A, int i, int j) {
    final int temp = A[i];
    A[i] = A[j];
    A[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]:
    def heapSort(A: list[int]) -> None:
      def maxHeapify(A: list[int], i: int, heapSize: int) -> None:
        l = 2 * i + 1
        r = 2 * i + 2
        largest = i
        if l < heapSize and A[largest] < A[l]:
          largest = l
        if r < heapSize and A[largest] < A[r]:
          largest = r
        if largest != i:
          A[largest], A[i] = A[i], A[largest]
          maxHeapify(A, largest, heapSize)

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

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

    heapSort(nums)
    return nums

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>& A, int l, int r) {
    if (l >= r)
      return;

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

  int partition(vector<int>& A, int l, int r) {
    const int randIndex = rand() % (r - l + 1) + l;
    swap(A[randIndex], A[r]);
    const int pivot = A[r];
    int nextSwapped = l;
    for (int i = l; i < r; ++i)
      if (A[i] <= pivot)
        swap(A[nextSwapped++], A[i]);
    swap(A[nextSwapped], A[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[] A, int l, int r) {
    if (l >= r)
      return;

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

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

  private void swap(int[] A, int i, int j) {
    final int temp = A[i];
    A[i] = A[j];
    A[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]:
    def quickSort(A: list[int], l: int, r: int) -> None:
      if l >= r:
        return

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

      m = partition(A, l, r)
      quickSort(A, l, m - 1)
      quickSort(A, m + 1, r)

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