Sort an Array

In this article, we will explore various approaches to solving this problem. We’ll discuss some of the most popular sorting algorithms, their time and space complexities, and their suitability for this problem. So, let’s roll up our sleeves and get to work!

Problem Statement:

Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

We will implement two sorting algorithms, Merge Sort and Quick Sort to sort the input array in O(N \ Log(N)) time and O(N)* Space.

---

Approach 1: Merge Sort

Merge sort is a divide-and-conquer algorithm that breaks the array into smaller sub-arrays until each sub-array contains only one element. Then, it merges the sub-arrays back together in sorted order, until the entire array is sorted.

1. Divide the Array - The first step is to divide the array into smaller sub-arrays until each sub-array contains only one element. We do this by recursively dividing the array in half until we can’t divide it any further.

2. Merge the Sub-Arrays - Once we have divided the array into single-element sub-arrays, we merge them in sorted order. We do this by comparing the first element of each sub-array and placing them in order in a new array. We repeat this process until all the sub-arrays are merged into a single sorted array.

// ES6 Arrow Function
const mergeSort = arr => {
    // Base Case - if the array has less than 2 elements, it's already sorted
    if(arr.length < 2) return arr;

    // Split the array into two halves 
    let middleIndex = Math.floor(arr.length / 2);
    let leftHalf = arr.slice(0, middleIndex);
    let rightHalf = arr.slice(middleIndex);

    // Recursively sort each half
    const sortedLeftHalf = mergeSort(leftHalf);
    const sortedRightHalf = mergeSort(rightHalf);

    // Merge the sorted halves back
    return merge(sortedLeftHalf, sortedRightHalf);
}

const merge = (leftArr, rightArr) => {
    let mergedArr = [];
    let leftIndex = 0, rightIndex = 0;

    // Iterate through both arrays adding the smaller elements in the merged array
    while(leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if(leftArr[leftIndex] < rightArr[rightIndex]) {
            mergedArr.push(leftArr[leftIndex]);
            leftIndex++;
        } else {
            mergedArr.push(rightArr[rightIndex]);
            rightIndex++;
        }
    }

    // Add the remaining elements from the left array
    while(leftIndex < leftArr.length) {
        mergedArr.push(leftArr[leftIndex]);
        leftIndex++;
    }

    // Add the remaining elements from the right array
    while(rightIndex < rightArr.length) {
        mergedArr.push(rightArr[rightIndex]);
        rightIndex++;
    }

    return mergedArr;
}

Time Complexity: O(N * Log(N))

Space Complexity: O(N)

---

Approach 2: Quick Sort

Quick sort is also a divide-and-conquer algorithm that picks a “pivot” element and partitions the array around the pivot, such that all elements on the left side of the pivot are less than or equal to the pivot, and all elements on the right side of the pivot are greater than the pivot. Then, it recursively applies the same partitioning process to the left and right sub-arrays until the entire array is sorted.

1. Choose a Pivot - The first step of the quick sort algorithm is to choose a pivot element from the array. There are many ways to choose a pivot element, but the most common approach is to choose the first or last element of the array.

2. Partition the Array - Once we have chosen the pivot element, we partition the array around the pivot. We do this by scanning the array from both ends and swapping elements that are on the wrong side of the pivot. We repeat this process until all elements on the left side of the pivot are less than or equal to the pivot, and all elements on the right side of the pivot are greater than the pivot.

3. Recursively Sort the Sub-Arrays - Once we have partitioned the array, we recursively apply the same partitioning process to the left and right sub-arrays until the entire array is sorted.

// ES6 Arrow Function
const quickSort = arr => {
    // Base case: if the array has less than 2 elements then it's already sorted
    if(arr.length < 2) return arr;

    // Choose a pivot
    const pivot = arr[0];

    // Divide the array in 2 parts: Elements <= pivot and Elements > pivot
    const lessThanPivot = [], greaterThanPivot = [];

    for(let i = 1; i < arr.length; i++) {
        if(arr[i] <= pivot) lessThanPivot.push(arr[i]);
        else greaterThanPivot.push(arr[i]);
    }

    // Recursively sort the partitions
    const sortedLessThanPivot = quickSort(lessThanPivot);
    const sortedGreaterThanPivot = quickSort(greaterThanPivot);

    // Concatenate the sorted partition and the pivot element 
    return sortedLessThanPivot.concat([pivot], sortedGreaterThanPivot);
}

Time Complexity: O(N * Log(N))

Space Complexity: O(N)

---

And there you have it guys! We’ve explored two approaches to solve this problem and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 912