---
tags: leetcode
---

# [912. Sort an Array](https://leetcode.com/problems/sort-an-array/)
---
# My Solution
## Solution 1: Quick Sort (TLE)
### The Key Idea for Solving This Coding Question
### C++ Code

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

        return nums;
    }

private:
    void quickSort(vector<int> &nums, int left, int right) {
        if (left < right) {
            int pivotIdx = partition(nums, left, right);
            quickSort(nums, left, pivotIdx - 1);
            quickSort(nums, pivotIdx + 1, right);
        }
    }

    int partition(vector<int> &nums, int left, int right) {
        int i = left - 1;
        int x = rand() % (right - left + 1) + left;
        swap(nums[x], nums[right]);

        int pivot = nums[right];
        for (int j = left; j <= right; ++j) {
            if (nums[j] < pivot) {
                swap(nums[++i], nums[j]);
            }
        }
        swap(nums[++i], nums[right]);

        return i;
    }
};

### Time Complexity
* Best Case:
$O(nlogn)$
$n$ is the length of `nums`.
The best case of quick sort is when we will select pivot as a mean element.
Because we have selected mean element as pivot, the array will be divided in partitions of equal size so that the height of the tree will be mininum.
* Worst Case
$O(n^{2})$
$n$ is the length of `nums`.
This will happen when our array is sorted and we select the smallest or largest element as pivot.
* Average Case:
$O(nlogn)$
$n$ is the length of `nums`.
### Space Complexity
* Best Case:
$O(logn)$
$n$ is the length of `nums`.
* Worst Case:
$O(n)$
$n$ is the length of `nums`.
### Reference:
[Time and Space complexity of Quick Sort](https://iq.opengenus.org/time-and-space-complexity-of-quick-sort/)
[Comparison Sort: Quick Sort(快速排序法)](https://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html)
[Quicksort: Design, Implementation and Time Complexity Analysis](https://www.enjoyalgorithms.com/blog/quick-sort-algorithm)
## Solution 2: Merge Sort
### The Key Idea for Solving This Coding Question
### C++ Code

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

private:
    void mergeSort(vector<int> &nums, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;
            mergeSort(nums, left, middle);
            mergeSort(nums, middle + 1, right);
            merge(nums, left, middle, right);
        }
    }

    void merge(vector<int> &nums, int left, int middle, int right) {
        vector<int> leftSubarray, rightSubarray;
        for (int i = left; i <= middle; ++i) {
            leftSubarray.push_back(nums[i]);
        }
        leftSubarray.push_back(INT_MAX);

        for (int i = middle + 1; i <= right; ++i) {
            rightSubarray.push_back(nums[i]);
        }
        rightSubarray.push_back(INT_MAX);

        int l = 0, r = 0;
        for (int k = left; k <= right; ++k) {
            if (leftSubarray[l] <= rightSubarray[r]) {
                nums[k] = leftSubarray[l];
                ++l;
            } else {
                nums[k] = rightSubarray[r];
                ++r;
            }
        }
    }
};

### Time Complexity
$O(nlogn)$
$n$ is the length of `nums`.
### Space Complexity
$O(n)$
$n$ is the length of `nums`.
### Reference
[Merge sort time and space complexity](https://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity)
## Solution 3: Heap Sort
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int> &nums) {
        buildHeap(nums);
        heapSort(nums);
        return nums;
    }
    
private:
    void buildHeap(vector<int> &nums) {
        for (int parentIdx = (nums.size() >> 1) - 1; parentIdx >= 0; --parentIdx) {
            maxHeapify(nums, parentIdx, nums.size());
        }
    }
    
    void maxHeapify(vector<int> &nums, int rootIdx, int len) {
        int maxIdx = rootIdx, leftIdx = (rootIdx << 1) + 1, rightIdx = (rootIdx << 1) + 2;
        
        if (leftIdx < len && nums[maxIdx] < nums[leftIdx]) {
            maxIdx = leftIdx;
        }
        
        if (rightIdx < len && nums[maxIdx] < nums[rightIdx]) {
            maxIdx = rightIdx;
        }
        
        if (maxIdx != rootIdx) {
            swap(nums[maxIdx], nums[rootIdx]);
            maxHeapify(nums, maxIdx, len);
        }
    }
    
    void heapSort(vector<int> &maxHeap) {
        for (int i = maxHeap.size() - 1; i >= 0; --i) {
            swap(maxHeap[0], maxHeap[i]);
            maxHeapify(maxHeap, 0, i);
        }
    }
};

### Time Complexity
* Best Case:
$O(n)$
$n$ is the length of `num`.
This is the runtime when everything in the input is identical.
* Worst Case:
$O(nlogn)$
$n$ is the length of `num`.
* Average Case:
$O(nlogn)$
$n$ is the length of `num`.
### Space Complexity
$O(1)$
### Reference
[Heapsort Algorithm](https://www.interviewcake.com/concept/java/heapsort)
## Solution 4: Shell Sort
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int span = nums.size() / 2, len = nums.size();
        
        while (span >= 1) {
            int j = span;
            while (j < len) {
                int tmp = nums[j], i = j - span;
                while (i >= 0 && nums[i] > tmp) {
                    nums[i + span] = nums[i];
                    i -= span;
                }
                nums[i + span] = tmp;
                ++j;
            }
            span /= 2;
        }
        
        return nums;
    }
};

### Time Complexity
* Best Case:
$O(nlogn)$
$n$ is the length of `num`.
* Worst Case:
$O(n^{2})$
$n$ is the length of `num`.
* Average Case:
$O(nlogn)$ or $O(n^{1.25})$
$n$ is the length of `num`.
### Space Complexity
$O(1)$
## Solution 5: Insertion Sort (TLE)
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int j = 1; j < nums.size(); ++j) {
            // nums[0..i] is the sorted subarray.
            // nums[j..len-1] is the unsorted subarray.
            int i = j - 1;
            int key = nums[j];
            while (i >= 0 && nums[i] > key) {
                nums[i + 1] = nums[i];
                --i;
            }
            // case 1: i < 0
            // case 2: nums[i] <= key
            
            if (i < 0) {
                // The original subarray, nums[0..i], was 
                // sorted and key is less than nums[0].
                nums[i + 1] = key;
            } else {
                // Now, nums[i] <= key and we have move the original
                // subarray, nums[i+1 .. j-1], to nums[i+1 .. j].
                // nums[i+1] is the right position for key to make
                // the new sorted subarray, nums[0..j]
                nums[i + 1] = key;
            }
        }
        return nums;
    }
};

### Time Complexity
* Worst Case (輸入資料反向排序)
$O(n^{2})$
* Average Case
$O(n^{2})$
* Best Case (輸入資料已排序完成)
$O(n)$
### Space Complexity
$O(1)$
# Miscellaneous
<!--
# Test Cases

[5,2,3,1]

[5,1,1,2,0,0]

* Wrong Answer:

[5,2,6]

* TLE:
https://leetcode.com/submissions/detail/557406501/testcase/
* TLE:
https://leetcode.com/submissions/detail/796986621/testcase/
* TLE:
https://leetcode.com/submissions/detail/800279266/testcase
-->