Merge Sort (Simple way to understanding Merge Sort)

Igiraneza Honorine — Sat, 03 Sep 2022 13:45:10 +0000

We are provided with an array with items and break down this array until each item is separated with each other and sorted. After that, they are merged to return the combined array of items sorted. That’s what merge sort is going to be doing.
So simple! Let’s get started without further ado.

We start comparing items with each other, if an item is less than another, it goes to the combined array and increment index of the array of that smaller item.

Diagrams below explain well the algorithm used to quickly sort with merge.

function merge(array1, array2) {
    let combined = []
    let i = 0
    let j = 0
    while(i < array1.length && j < array2.length) {
        if(array1[i] < array2[j]) {
            combined.push(array1[i])
            i++
        } else {
            combined.push(array2[j])
            j++
        }
    }
    while(i < array1.length) {
        combined.push(array1[i])
        i++
    }
    while(j < array2.length) {
        combined.push(array2[j])
        j++
    }
    return combined
}

function mergeSort(array) {
    if(array.length === 1) return array

    let mid = Math.floor(array.length/2)
    let left = array.slice(0,mid)
    let right = array.slice(mid)

    return merge(mergeSort(left), mergeSort(right))
}

Test Merge sort by calling this function: mergeSort([1,3,7,8,2,4,5,6])

The easiest way to understanding Quick Sort🔥

Igiraneza Honorine — Thu, 01 Sep 2022 16:14:18 +0000

Quick sort has been an algorithm I was afraid of learning😢, pretending that it is too hard and require too much time to understand it, but now here I am explaining to you how straight forward it is using a short article written for it. Simple recursive function is required to fully understand quick sort.

The first thing to know is that we use pivot point while comparing to other items in order to get the left side and right side of pivot and repeat the process. With that information we can get started.

Here I use pivotIndex variable to compare item on that index with other items, swapIndex variable to track index which will be swapped with small item found on the left side of pivot, and variable i to loop through all items and know which current item we are comparing to the pivot.

swapIndex is initially set at the same index of pivotIndex. Whenever item smaller than pivot item is found, we increment 1 to swapIndex and swap item on swap index with current item we are on while looping with i. After that we swap pivot item with item on swap index.

Swap function

function swapFn(array, firstIndex, secondIndex) {
    let temp = array[firstIndex]
    array[firstIndex] = array[secondIndex]
    array[secondIndex] = temp
}

Below is the algorithm that we use recursively to sort elements with Quick sort.
Quick Sort algorithm
Step 1: Start
Step 2: Declare variables pivotIndex, swapIndex and i.
Step 3: Initialize variables pivotIndex←0 swapIndex← pivotIndex, i= pivotIndex +1

Step 4: Repeat the steps until i≤array.length-1
if array[i] is less than array[pivotIndex] then
swapIndex++
swapFn(array[swap], array[i])
swapFn(array[swapIndex], array[pivotIndex])
Step 5: OUTPUT swapIndex
Step 6: Stop

Swap Index where pivot will be swapped function

function pivotFn(array, pivotIndex=0, endIndex=array.length-1) { 
    let swapIndex = pivotIndex
    for (let i = pivotIndex + 1; i <= endIndex; i++) {
        if (array[i] < array[pivotIndex]) {
            swapIndex++
            swapFn(array, swapIndex, i)
        }
    }
    swapFn(array, pivotIndex, swapIndex)
    return swapIndex
}

Follow along this diagram to see how it works.

function quickSort(array, left=0, right=array.length-1) {
if(left < right) {
let pivotIndex = pivot(array, left, right)
quickSort(array, left, pivotIndex-1)
quickSort(array, pivotIndex+1, right)
}
return array
}

Test Quick sort by calling this function: quickSort([4,6,1,7,3,2,5])

To sum up, We’ve got the left side with red color and the right side with green color. We do the same above process to both sides by comparing items with the pivot and swap if item is less than the pivot and then swap the pivot with the swap index.

DEV Community: Igiraneza Honorine

Merge Sort (Simple way to understanding Merge Sort)

The easiest way to understanding Quick Sort🔥

Swap function

Swap Index where pivot will be swapped function