Merge Sort

Sort an array using Merge Sort algorithm.

Medium

Examples

Example 1: [5,2,3,1] → [1,2,3,5]

Implementation

Ruby


  # 3. Sorting: Merge Sort
  # Problem Statement:
  # Sort an array using Merge Sort algorithm.
  # Input: [5,2,3,1]
  # Output: [1,2,3,5]
  # Time Complexity: O(n log n)
  def self.merge_sort(arr)
    return arr if arr.size <= 1

    mid = arr.size / 2
    left = merge_sort(arr[0...mid])
    right = merge_sort(arr[mid..-1])

    merge(left, right)

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Patterns & Techniques

Divide and Conquer Sorting

Problem Details

Category: Binary Search And Sorting

Difficulty: Medium

Module: BinarySearchAndSorting

Method: self.merge_sort