Merge Sort: A Stable and Efficient Sorting Algorithm

Merge Sort is a powerful sorting algorithm that guarantees a stable and efficient sorting process, even for large datasets. It uses a divide-and-conquer approach, recursively breaking down the array into smaller sub-arrays before merging them back together in sorted order. In this article, I’ll explore how Merge Sort works, provide a detailed implementation, and discuss its time and space complexity.

How Merge Sort Works

Merge Sort operates by dividing the array into smaller sub-arrays, sorting those sub-arrays, and then merging them back together. This process continues recursively until the entire array is sorted.

Key Concepts

1. Divide and Conquer: The array is divided into two halves until each sub-array contains a single element.
2. Merging: The sub-arrays are then merged back together in sorted order.
3. Recursion: Merge Sort is a recursive algorithm that continues to divide and merge until the array is fully sorted.

For a visual representation of how Merge Sort operates, check out this video.

Implementation

Here’s a TypeScript implementation of Merge Sort:

export const mergeSort = (array: number[]): number[] => {
  if (array.length <= 1) {
    return array; // An array of length 0 or 1 is already sorted
  }

  const middleIndex = Math.floor(array.length / 2);
  const leftArray = array.slice(0, middleIndex);
  const rightArray = array.slice(middleIndex);

  const sortedLeftArray = mergeSort(leftArray);
  const sortedRightArray = mergeSort(rightArray);

  return merge(sortedLeftArray, sortedRightArray);
};

const merge = (leftArray: number[], rightArray: number[]): number[] => {
  const sortedArray: number[] = [];

  // While there are elements in both left and right arrays
  while (leftArray.length && rightArray.length) {
    const arrayToShift = leftArray[0] < rightArray[0] ? leftArray : rightArray;
    sortedArray.push(arrayToShift.shift()!);
  }

  // If there are remaining elements in either left or right array, add them to the sorted array
  return [...sortedArray, ...leftArray, ...rightArray];
};

Explanation of the Implementation

1. Base Case: The base case checks if the array length is 1 or less. If true, the array is already sorted and is returned as-is.
2. Divide: The array is divided into two halves using the middle index. This process continues recursively until each sub-array has a single element.
3. Merge Function: The merge function combines the sorted sub-arrays by comparing the elements at the start of each sub-array and merging them into a new array in sorted order. The remaining elements are then added to the sorted array.
4. Recursive Merging: The sorted left and right sub-arrays are merged to produce the fully sorted array.

Time and Space Complexity

Time Complexity

• Worst-case: O(n log n) => Merge Sort consistently divides the array into two halves and then merges them back, resulting in O(n log n) time complexity.
• Best-case: O(n log n) => Even in the best case, the algorithm needs to divide and merge, maintaining O(n log n) complexity.
• Average-case: O(n log n) => On average, Merge Sort performs at O(n log n) due to the consistent nature of its divide-and-conquer strategy.

Space Complexity

• Space Complexity: O(n) => Merge Sort requires additional space proportional to the size of the array being sorted, as it needs space for the temporary sub-arrays during the merging process.

Further Reading

For more insights into sorting algorithms, explore our detailed posts on other classic algorithms:

• Bubble Sort: Learn about this simple algorithm that repeatedly compares and swaps adjacent elements.
• Selection Sort: Discover how Selection Sort finds and places the minimum element in its correct position.
• Insertion Sort: Explore how Insertion Sort builds the final sorted array one item at a time.
• Quick Sort: Understand the efficiency of Quick Sort’s divide-and-conquer approach.

Conclusion

Merge Sort is a stable and efficient sorting algorithm, making it a popular choice for sorting large datasets. Its consistent O(n log n) time complexity, combined with its ability to handle large datasets without significant performance degradation, makes it a powerful tool for developers.

Whether you’re dealing with complex data structures or optimizing sorting processes, Merge Sort is an essential algorithm to understand and implement.