merge sort

Merge Sort

Generate Random Numbers

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Merge Sort Overview

History

Merge sort was invented by John von Neumann in 1945. It is a classic divide-and-conquer algorithm that is particularly effective for large datasets and is widely used in computer science and programming.

Current Uses

  • Large Data Sets: Often employed for sorting large datasets where performance is critical.
  • Stable Sort: Utilized in applications where stable sorting is required.
  • External Sorting: Commonly used in external sorting algorithms for managing large files that do not fit into memory.

Time and Space Complexity

Time Complexity

  • Best Case: O(n log n) – Consistent performance across all cases.
  • Average Case: O(n log n) – Maintains efficient performance on average.
  • Worst Case: O(n log n) – Efficient even in the worst-case scenario.

Space Complexity

Space Complexity: O(n) – Requires additional space for the temporary arrays used in the merging process.

Pseudo Code

function mergeSort(arr):
    if length(arr) <= 1:
        return arr
    mid = length(arr) / 2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:length(arr)])
    return merge(left, right)

function merge(left, right):
    result = []
    while left and right are not empty:
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0]
        else:
            append right[0] to result
            remove right[0]
    append remaining elements of left and right to result
    return result

Key Characteristics

  • Stable: Merge sort is a stable sorting algorithm.
  • Divide and Conquer: The algorithm utilizes the divide-and-conquer strategy effectively.

Summary

Merge sort is a powerful and efficient sorting algorithm that consistently performs at O(n log n) complexity. Its stability and performance make it ideal for sorting large datasets and is widely utilized in computer science applications.

Merge Sort Code Implementation