Katkat
Back

Implement Merge Sort

J.P. MorganSoftware Engineer II · Onsite
MediumSoftware Engineer IIOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement the Divide and Conquer paradigm, specifically the recursive merge sort algorithm, while maintaining stability and managing auxiliary space.

Problem Statement

Implement the merge_sort algorithm to sort an array of integers in non-decreasing order. Your implementation must be stable (preserving the relative order of duplicate elements) and run in O(n log n) time complexity.

Function Signature

def merge_sort(nums: list[int]) -> list[int]:
    # Implementation here

Constraints

  • n (length of array) is between 0 and 10^5.
  • The values in the array can range from -10^9 to 10^9.
  • You should aim for O(n) auxiliary space complexity.

Examples

Example 1: Input: [38, 27, 43, 3, 9, 82, 10] Output: [3, 9, 10, 27, 38, 43, 82]

Example 2: Input: [5, 2, 5, 1] Output: [1, 2, 5, 5] Note: The stability ensures the first '5' appearing in the input remains before the second '5' in the output.

Edge Cases

  • Empty array or array with a single element.
  • Arrays with all identical elements.
  • Arrays already sorted or sorted in reverse order.

Hints

Hint 1

Divide the array into two halves recursively until each sub-array has a size of one.

Hint 2

Use a helper function to merge two sorted sub-arrays into a single sorted array by comparing the smallest elements of each sub-array.

Hint 3

During the merge step, always take the element from the left sub-array if it is less than or equal to the element from the right sub-array to ensure stability.

Follow-up questions

  • How does the space complexity change if you perform the sort in-place versus using a temporary array for merging?
  • Can you modify the algorithm to sort a linked list instead of an array, and what are the advantages of doing so?
  • How does the performance of merge sort compare to quicksort in terms of worst-case complexity and memory usage?