# Sort an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-an-array)
Canonical: https://scaleengineer.com/dsa/problems/sort-an-array
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort), [Radix Sort](https://scaleengineer.com/algorithms/radix-sort), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys), [Hive](https://scaleengineer.com/companies/hive)
---
## Problem
Given an array of integers `nums`, sort the array in ascending order and return it.

You must solve the problem **without using any built-in** functions in `O(nlog(n))` time complexity and with the smallest space complexity possible.

**Example 1:**

**Input:** nums = [5,2,3,1]
**Output:** [1,2,3,5]
**Explanation:** After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

**Example 2:**

**Input:** nums = [5,1,1,2,0,0]
**Output:** [0,0,1,1,2,5]
**Explanation:** Note that the values of nums are not necessarily unique.

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `-5 * 104 <= nums[i] <= 5 * 104`

# Approaches
## Bubble Sort
Bubble Sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The passes through the list are repeated until the list is sorted. While simple to understand, its performance is poor for large datasets, making it impractical for this problem's constraints.
**Time:** `O(n^2)` - In the worst and average cases, there are two nested loops, leading to a quadratic time complexity. The best case is `O(n)` if the array is already sorted and the optimization is used. · **Space:** `O(1)` - The sort is performed in-place, requiring only a constant amount of extra space for a temporary variable during swaps.
**Pros:** Simple to understand and implement.; Space efficient (`O(1)`).
**Cons:** Highly inefficient for large arrays, with a time complexity of `O(n^2)`.; Fails to meet the `O(n log n)` time complexity requirement of the problem.
### Explanation
The algorithm works by making multiple passes through the array. In each pass, it compares each pair of adjacent items and swaps them if they are in the wrong order. This process effectively "bubbles" the largest unsorted element up to its correct position at the end of the array. An optimization can be made: if a complete pass is made without any swaps, the array is already sorted, and the algorithm can terminate early.
```java
class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    // swap nums[j] and nums[j+1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no two elements were swapped by inner loop, then break
            if (!swapped) {
                break;
            }
        }
        return nums;
    }
}
```
### Algorithm
- Iterate from `i = 0` to `n-2`.
- In an inner loop, iterate from `j = 0` to `n-i-2`.
- Compare `nums[j]` with `nums[j+1]`.
- If `nums[j] > nums[j+1]`, swap them.
- After each outer loop iteration, the i-th largest element is placed at its correct position.

## Quick Sort
Quick Sort is a highly efficient, divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. While its average-case performance is excellent, its worst-case performance is `O(n^2)`, which does not satisfy the problem's strict time complexity requirement.
**Time:** `O(n log n)` on average. The partitioning takes `O(n)` time. If the pivot consistently divides the array into two roughly equal halves, the recursion depth is `O(log n)`. The worst-case complexity is `O(n^2)` if the pivot choices are consistently poor. · **Space:** `O(log n)` on average for the recursion call stack. The worst-case space complexity is `O(n)`.
**Pros:** Very fast in practice, often outperforming other `O(n log n)` algorithms.; In-place sorting (Lomuto partition scheme), leading to low space overhead (`O(log n)`).
**Cons:** Worst-case time complexity is `O(n^2)`, which violates the problem's requirement.; Not a stable sort (the relative order of equal elements may change).
### Explanation
The key to Quick Sort is the `partition()` function. This function takes an array and a pivot element, and rearranges the array such that all elements smaller than the pivot are on its left, and all elements greater are on its right. The pivot is then in its final sorted position. This process is applied recursively to the sub-arrays. The choice of pivot is crucial; a poor choice (like always picking the first or last element in an already sorted array) leads to the `O(n^2)` worst case. Randomizing the pivot choice can help avoid this. The implementation below uses the Lomuto partition scheme with a randomized pivot to improve performance.
```java
import java.util.Random;

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

    private void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int pi = partition(nums, low, high);
            quickSort(nums, low, pi - 1);
            quickSort(nums, pi + 1, high);
        }
    }

    private int partition(int[] nums, int low, int high) {
        Random rand = new Random();
        int pivotIndex = low + rand.nextInt(high - low + 1);
        swap(nums, pivotIndex, high);

        int pivot = nums[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, high);
        return i + 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```
### Algorithm
- Define a recursive function `quickSort(arr, low, high)`.
- The base case for the recursion is `low >= high`.
- Choose a pivot element. A common strategy is to pick the last element, or a random element to avoid worst-case scenarios.
- Partition the array around the pivot. All elements smaller than the pivot are moved to its left, and all greater elements to its right. Let the pivot's final index be `pi`.
- Recursively call `quickSort(arr, low, pi - 1)`.
- Recursively call `quickSort(arr, pi + 1, high)`.

## Merge Sort
Merge Sort is a classic divide-and-conquer algorithm that guarantees an `O(n log n)` runtime. It works by recursively dividing the array into halves until each sub-array contains a single element, and then merges these sub-arrays back together in sorted order.
**Time:** `O(n log n)` - The recurrence relation is T(n) = 2T(n/2) + O(n), which resolves to `O(n log n)`. This holds for the worst, average, and best cases. · **Space:** `O(n)` - The `merge` step requires an auxiliary array of the same size as the input array to store the elements while merging.
**Pros:** Guaranteed `O(n log n)` time complexity, making it reliable.; It is a stable sort.
**Cons:** Requires `O(n)` extra space, which can be a significant drawback for very large arrays or in memory-constrained environments. It does not meet the "smallest space complexity" part of the problem's requirement.
### Explanation
The algorithm has two main parts: the recursive division and the merging.
1. **Divide**: The `mergeSort` function recursively splits the array in half until it can no longer be divided (i.e., the sub-array has 0 or 1 elements, which is inherently sorted).
2. **Merge**: The `merge` function is the core of the algorithm. It takes two sorted sub-arrays and combines them into a single sorted array. It does this by creating temporary arrays to hold the sub-arrays and then iteratively comparing the elements of the temporary arrays, placing the smaller element into the original array. This merging step requires extra space.
```java
class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, temp, left, mid);
            mergeSort(nums, temp, mid + 1, right);
            merge(nums, temp, left, mid, right);
        }
    }

    private void merge(int[] nums, int[] temp, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[k++] = temp[i++];
            } else {
                nums[k++] = temp[j++];
            }
        }

        while (i <= mid) {
            nums[k++] = temp[i++];
        }
    }
}
```
### Algorithm
- Define a recursive function `mergeSort(arr, left, right)`.
- The base case is `left >= right`.
- Find the middle point: `mid = (left + right) / 2`.
- Recursively call `mergeSort(arr, left, mid)`.
- Recursively call `mergeSort(arr, mid + 1, right)`.
- Call a `merge(arr, left, mid, right)` function to merge the two sorted halves.

## Heap Sort
Heap Sort is an efficient, in-place sorting algorithm that leverages a binary heap data structure. It meets both the `O(n log n)` time complexity and the minimal space complexity requirements of the problem, making it an optimal solution.
**Time:** `O(n log n)` - Building the initial heap takes `O(n)` time. Then, `n-1` elements are extracted from the heap. Each extraction involves a swap and a `heapify` operation, which takes `O(log k)` time where `k` is the heap size. This results in a total time complexity of `O(n log n)`. · **Space:** `O(1)` - The sort is performed in-place. The recursive `heapify` function uses `O(log n)` stack space in the worst case, but it can be implemented iteratively to achieve true `O(1)` space.
**Pros:** Guaranteed `O(n log n)` worst-case time complexity.; Space complexity is `O(1)`, making it very memory-efficient.; Perfectly satisfies all constraints of the problem.
**Cons:** Not a stable sort.; Can be slower in practice than a well-implemented Quick Sort due to poor cache locality.
### Explanation
The algorithm consists of two main phases:
1. **Heapify Phase**: The input array is converted into a max heap. A max heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. This can be done efficiently in `O(n)` time by starting from the last non-leaf node and repeatedly calling a `heapify` function to satisfy the heap property.
2. **Sortdown Phase**: The largest element is at the root of the max heap. It is swapped with the last element of the heap (the end of the array), and the heap size is reduced by one. The `heapify` function is then called on the root to restore the max heap property. This process of swapping and heapifying is repeated until the heap is empty, resulting in a sorted array.
```java
class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;

        // Build max heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, n, i);
        }

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;

            // call max heapify on the reduced heap
            heapify(nums, i, 0);
        }
        return nums;
    }

    void heapify(int[] nums, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && nums[left] > nums[largest]) {
            largest = left;
        }

        if (right < n && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != i) {
            int swap = nums[i];
            nums[i] = nums[largest];
            nums[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(nums, n, largest);
        }
    }
}
```
### Algorithm
- Build a max heap from the input array. This is done by calling a `heapify` function for all non-leaf nodes, starting from the last one and moving up to the root.
- Loop from `i = n-1` down to `1`:
  - Swap the root of the heap (`nums[0]`) with the current last element (`nums[i]`)
  - Reduce the considered heap size by one.
  - Call `heapify` on the root (`index 0`) to restore the max heap property for the reduced heap.
- The array is now sorted.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
public
  int[] sortArray(int[] nums) {
    this.nums = nums;
    quikcSort(0, nums.length - 1);
    return nums;
  }
private
  void quikcSort(int l, int r) {
    if (l >= r) {
      return;
    }
    int x = nums[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
      while (nums[++i] < x) {
      }
      while (nums[--j] > x) {
      }
      if (i < j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    quikcSort(l, j);
    quikcSort(j + 1, r);
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var sortArray = function (
  nums,
) {
  function quickSort(l, r) {
    if (l >= r) {
      return;
    }
    let i = l - 1;
    let j = r + 1;
    const x = nums[(l + r) >> 1];
    while (i < j) {
      while (nums[++i] < x);
      while (nums[--j] > x);
      if (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
    quickSort(l, j);
    quickSort(j + 1, r);
  }
  const n = nums.length;
  quickSort(0, n - 1);
  return nums;
};

```

### Python

```python
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(l, r): if l >= r: return x = nums[randint(l, r)] i, j, k = l - 1, r + 1, l while k < j: if nums[k] < x: nums[i + 1], nums[k] = nums[k], nums[i + 1] i, k = i + 1, k + 1 elif nums[k] > x: j -= 1 nums[j], nums[k] = nums[k], nums[j] else: k = k + 1 quick_sort(l, i) quick_sort(j, r) quick_sort(0, len(nums) - 1) return nums

```

### CPP

```cpp
class Solution {
public:
  vector<int> sortArray(vector<int> &nums) {
    function<void(int, int)> quick_sort = [&](int l, int r) {
      if (l >= r) {
        return;
      }
      int i = l - 1, j = r + 1;
      int x = nums[(l + r) >> 1];
      while (i < j) {
        while (nums[++i] < x) {
        }
        while (nums[--j] > x) {
        }
        if (i < j) {
          swap(nums[i], nums[j]);
        }
      }
      quick_sort(l, j);
      quick_sort(j + 1, r);
    };
    quick_sort(0, nums.size() - 1);
    return nums;
  }
};

```