# 8. Sort Array nlogn

## 8. Sort an Array

[Sort an Array - LeetCode](https://leetcode.com/problems/sort-an-array/description/)

### Quick Sort with 1 pivot: `failed` → worst O(n^2)

> Time: Time over

> Space:

```jsx
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(arr, left, right) {
    if (left >= right) {
        return arr;
    }

    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
    return arr;
}

function partition(arr, left, right) {
    let pivot = right;
    let pointer = left;
    while (left < pivot) {
        if (arr[left] < arr[pivot]) {
            swap(arr, pointer, left);
            pointer++;
            console.log(pointer)
        }
        left++;
    }
    swap(arr, pointer, pivot);

    return pointer;
}

function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
    return arr;
}
```

### Quick Sort with 2 pivots ⇒ good when duplicates

[One-Pivot Quick Sort and Three-Way Partition Quick Sort for Duplicates, w. Explanation | 36 ms, Java - Sort an Array - LeetCode](https://leetcode.com/problems/sort-an-array/solutions/3217257/one-pivot-quick-sort-and-three-way-partition-quick-sort-for-duplicates-w-explanation-36-ms-java/)

```jsx
import java.util.Random;

class Solution {
    private static Random random;

    private static class Partition {
        int left;
        int right;
        Partition() {}
        Partition(int left, int right) {
            this.left = left; 
            this.right = right;
        }
    }
    
    public int[] sortArray(int[] nums) {
        random = new Random(1);
        Solution.quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            Partition partition = threeWayPartition(nums, start, end);
            quickSort(nums, start, partition.left - 1);
            quickSort(nums, partition.right + 1, end);
        }
    }

    private static Partition threeWayPartition(int[] nums, int start, int end) {
        int pivotIndex = start + random.nextInt(end - start + 1);
        int pivotValue = nums[pivotIndex];
        swap(nums, start, pivotIndex);

        // Loop invariant:
        // 1. [start, lt): strictly less than pivotValue
        // 2. [lt, cur) : equal to pivotValue
        // 3. [cur, gt] : unexplored
        // 4. (gt, end] : strictly larger than pivotValue
        int lt = start + 1;
        int cur = start + 1;
        int gt = end;
        while(cur <= gt) {
            if (nums[cur] < pivotValue) {
                swap(nums, lt, cur);
                lt++;
                cur++;
            } else if (nums[cur] == pivotValue) {
                cur++;
            } else if (nums[cur] > pivotValue) {
                swap(nums, cur, gt);
                gt--;
            }
        }
        // At exit, the partition is [start, lt), [lt, gt], (gt, end].
        return new Partition(lt, gt);
    }

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

}
```

### Merge Sort

> Time: O(nlogn)

> Space: O(N^2)

```jsx
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const arr = mergeSort(nums, 0, nums.length - 1);
    return arr;
};

function mergeSort(arr, s, e) {
    if ( s === e) 
        return [arr[s]];
    
    const m = s + Math.floor((e - s) / 2);
    const left = mergeSort(arr, s, m);
    const right = mergeSort(arr, m + 1, e);

    const merged = merge(left, right);
    return merged;
}

function merge(arr1, arr2) {
    let idx1 = 0;
    let idx2 = 0;

    const merged = [];
    while (idx1 < arr1.length && idx2 < arr2.length) {
        if (arr1[idx1] < arr2[idx2]) {
            merged.push(arr1[idx1]);
            idx1++;
        } else {
            merged.push(arr2[idx2]);
            idx2++;
        }
    }

    while (idx1 < arr1.length) {
        merged.push(arr1[idx1]);
        idx1++;
    }

    while (idx2 < arr2.length) {
        merged.push(arr2[idx2]);
        idx2++;
    }

    return merged;
}

function swap(arr, a, b) {
    [arr[b], arr[a]] = [arr[a], arr[b]];
}
```

using temp array

```jsx
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const arr = mergeSort(nums, 0, nums.length - 1);
    return arr;
};

function mergeSort(arr, s, e) {
    if (s >= e) {
        return arr;
    }
    const m = s + Math.floor((e - s) / 2);
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
    merge(arr, s, m, e);

    return arr;
}

function merge(arr, left, mid, right) {
    if (left >= right) {
        return arr;
    }

    const len = right - left + 1;
    const temp = new Array(len).fill(0);
    
    let i = left;
    let j = mid + 1;

    let pointer = 0;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[pointer] = arr[i];
            i++;
        } else {
            temp[pointer] = arr[j];
            j++;
        }
        pointer++;
    }

    while (i <= mid) {
        temp[pointer] = arr[i];
        i++;
        pointer++;
    }

    while (j <= right) {
        temp[pointer] = arr[j];
        j++;
        pointer++;
    }

    // replace
    for (let i = 0; i < len; i++) {
        arr[i + left] = temp[i];
    }

    // console.log(temp)

    return arr;
}

function mergeSort1(arr, s, e) {
    if ( s === e) 
        return [arr[s]];
    
    const m = s + Math.floor((e - s) / 2);
    const left = mergeSort(arr, s, m);
    const right = mergeSort(arr, m + 1, e);

    const merged = merge(left, right);
    return merged;
}

function merge1(arr1, arr2) {
    let idx1 = 0;
    let idx2 = 0;

    const merged = [];
    while (idx1 < arr1.length && idx2 < arr2.length) {
        if (arr1[idx1] < arr2[idx2]) {
            merged.push(arr1[idx1]);
            idx1++;
        } else {
            merged.push(arr2[idx2]);
            idx2++;
        }
    }

    while (idx1 < arr1.length) {
        merged.push(arr1[idx1]);
        idx1++;
    }

    while (idx2 < arr2.length) {
        merged.push(arr2[idx2]);
        idx2++;
    }

    return merged;
}

function swap(arr, a, b) {
    [arr[b], arr[a]] = [arr[a], arr[b]];
}
```

### Heap Sort

> Time: buildHeap: O(nlogn) remove: O(logn)

> Space: O(n)

```jsx
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    const minHeap = new Heap(nums);
    const arr = [];
    while (minHeap.heap.length !== 0) {
        arr.push(minHeap.remove());
    }

    return arr;
};

class Heap {
    constructor(arr, predicate = (a, b) => a <= b ? true : false) {
        this.predicate = predicate;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.siftUp(this.heap, this.heap.length - 1);
    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor(( currentIndex - 1) / 2 );
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }
            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor(( currentIndex - 1) / 2 );
        }
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;
        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            const flag = this.predicate(heap[currentIndex], heap[min]);
            if  (flag) break;

            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://algorithm.prettylog.com/algorithm-problems/daily-algorithms/8.-sort-array-nlogn.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.