Recursive

Merge Sort

Explanation

1. Break down the element into 1

Break stage
[4,55,23,3,8,10,1]

-> [4,55,23] , [3,8,10,1]

-> [4,55], [23] , [3,8] , [10,1]

-> [4] [55], [23] , [3] [8] , [10] [1]

2. Because the single element means sorted list. The next stage is merge two sorted list.

Merge stage

=> [4,55] [23] , [3,8] ,[1,10]

=> [4,23,55] , [1,3,8,10]

=> [1,3,4,8,10,23,55] 

Implementation

Average time complexity is O(nlogn)

function merge(leftList, rightList){
    const result = []
    
    while(leftList.length && rightList.length){
        if (leftList[0] < rightList[0]){
            result.push(leftList.shift())
        } else {
            result.push(rightList.shift())
        }
    }

    return result.concat(leftList, rightList)

}


function mergeSort(items){
    if (items.length < 2){
        return itmes
    }

    const middle = Math.floor(items.length / 2)
    const lh = items.splice(0, middle)
    const rh = items.splice(middle)

    return merge(mergeSort(lh), mergeSort(rh))
}

Quick Sort

Explanation

1. Find the last item as a pivot
2. Break down the list into left and right
3. Repeat the same method to the left and right list if the length greater than 2
4. Merge left and pivot and right

[4,55,3,8,10,1,23]

left => [4,3,8,10], pivot = 23, right => [55]

[4,3,8,10]

left => [4,3,8], pivot = 10 ,right => []

[4,3,8]

left => [4,3], pivot = 8 ,right => []

[4,3]

left => [], pivot = 3 ,right => [4]

Merge stage

=> [3,4]

=> [3,4,8]

=> [3,4,8,10]

=> [3,4,8,10,23,55]

Implementation

Average time complexity is O(nlogn)

function quickSort(items){
    if (items.length < 2){
        return itmes
    }

    const lastIdx = items.length - 1
    const pivot = itmes[lastIdx]
    const lh = []
    const rh = []

    for (let i = 0; i < lastIdx; i++){
        if(items[i] < pivot){
            lh.push(items[i])
        } else {
            rh.push(items[i])
        }
    }

    return [...quickSort(lh), pivot ,...quickSort(rh))
}