Sort an Array

LeetCode https://leetcode.cn/problems/sort-an-array/

Quicksort

class Solution {

    public int[] sortArray(int[] nums) {

        if (nums == null || nums.length <= 1) {
            return nums;
        }

        // quick sorting
        quickSortHelper(nums, 0, nums.length - 1);

        return nums;
    }
    
    public void quickSortHelper(int[] a, int lo, int hi) {

        if (hi <= lo)
            return;
        int pivot = partition(a, lo, hi);
        quickSortHelper(a, lo, pivot - 1);
        quickSortHelper(a, pivot + 1, hi);
    }

    public static int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int pivot = a[lo];
        while (true) {
            while (a[++i] < pivot)
                if (i == hi)
                    break;
            while (pivot < a[--j])
                if (j == lo)
                    break;
            if (i >= j)
                break;
            exch(a, i, j);
        }

        exch(a, lo, j);

        return j;
    }

    public static void exch(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

}

Complexity

• Time = O(nlog(n))
• Space = O(log(n))

---

Mergesort

Heapsort