Efficient Sorts (Merge Sort, Quick Sort)

Efficient Sorting Algorithms

Let's step up from the basic sorts to the heavy hitters: Merge Sort and Quick Sort. These algorithms use a "Divide and Conquer" strategy to achieve a much better time complexity of O(N log N) on average, making them suitable for sorting large datasets.

---

1. Merge Sort

Merge Sort is a classic example of a Divide and Conquer algorithm. It divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining.

• The Core Idea: Divide the list in half, recursively sort each half, and then merge the two sorted halves back together.

• Implementation:

  function mergeSort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
  
    const mid = Math.floor(arr.length / 2);
    const leftHalf = arr.slice(0, mid);
    const rightHalf = arr.slice(mid);
  
    const sortedLeft = mergeSort(leftHalf);
    const sortedRight = mergeSort(rightHalf);
  
    return merge(sortedLeft, sortedRight);
  }
  
  function merge(left, right) {
    let resultArray = [], leftIndex = 0, rightIndex = 0;
  
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
      } else {
        resultArray.push(right[rightIndex]);
        rightIndex++;
      }
    }
  
    return resultArray
      .concat(left.slice(leftIndex))
      .concat(right.slice(rightIndex));
  }
  

• Complexity:

  • Time: O(N log N) in all cases.
  • Space: O(N), as it requires extra space for the merged arrays.

---

2. Quick Sort

Quick Sort is another Divide and Conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

• The Core Idea: Pick a pivot, partition the array around the pivot, and recursively sort the partitions.

• Implementation (Lomuto partition scheme):

  function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
      const pivotIndex = partition(arr, low, high);
      quickSort(arr, low, pivotIndex - 1);  // Sort the left part
      quickSort(arr, pivotIndex + 1, high); // Sort the right part
    }
    return arr;
  }
  
  function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
  
    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its final place
    return i + 1;
  }
  

• Complexity:

  • Time: O(N log N) on average, but O(N^2) in the worst case (e.g., for already sorted data with a poor pivot selection strategy).
  • Space: O(log N) on average (due to the recursion stack), but O(N) in the worst case.

---

Key Takeaway: Merge Sort and Quick Sort are highly efficient, general-purpose sorting algorithms. Merge Sort offers guaranteed O(N log N) performance but requires extra space. Quick Sort is often faster in practice and sorts in-place, but its worst-case performance is O(N^2). The choice between them depends on the specific requirements of the problem.