Implement merge sort and largest 1-rectangle

The coding round included two algorithm questions:

1. Implement merge sort for an array of integers. Return the sorted array and explain its time and space complexity.
2. Given an m x n binary matrix containing only 0 and 1, find the area of the largest rectangular submatrix consisting entirely of 1s.

Assume standard input sizes and focus on correctness and efficiency.

Part 1: Implement Merge Sort for an Array of Integers

Given an array of integers, return a new array containing the same integers sorted in non-decreasing order. You should implement merge sort rather than using a built-in sorting function.

Constraints

• 0 <= len(nums) <= 100000
• -10^9 <= nums[i] <= 10^9
• Do not use built-in full-array sorting functions such as sorted(nums) or nums.sort().
• The returned array must contain exactly the same elements as the input array.

Examples

Example 1

Input: ([5, 2, 9, 1, 5, 6],)
Output: [1, 2, 5, 5, 6, 9]

Explanation: The values are sorted in non-decreasing order, preserving duplicates.

Example 2

Input: ([],)
Output: []

Explanation: Edge case: an empty array is already sorted.

Hints

1. Recursively split the array into two halves until each part has size 0 or 1.
2. The key step is merging two already-sorted halves in linear time.

Part 2: Find the Area of the Largest Rectangular Submatrix of 1s

Given an m x n binary matrix containing only 0s and 1s, find the area of the largest rectangular submatrix consisting entirely of 1s. The rectangle must be aligned with the rows and columns of the matrix.

Constraints

• 0 <= m <= 500
• 0 <= n <= 500
• matrix is rectangular: every row has the same length
• matrix[i][j] is either 0 or 1
• An empty matrix or a matrix with zero columns has answer 0.

Examples

Example 1

Input: ([[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]],)
Output: 6

Explanation: The largest all-1 rectangle has area 6, covering 2 rows and 3 columns.

Example 2

Input: ([],)
Output: 0

Explanation: Edge case: an empty matrix contains no rectangle.

Hints

1. Treat each row as the base of a histogram where each column height counts consecutive 1s ending at that row.
2. For each histogram, use a monotonic increasing stack to find the largest rectangle in linear time.