Quick Overview

Implement merge sort from first principles and return integers in nondecreasing order without a built-in sort. The exercise covers empty input, duplicates, negative values, multiset preservation, divide-and-merge structure, and the expected logarithmic recursion depth.

Implement Merge Sort and Return a Sorted Array

Company: Salesforce

Role: Member of Technical Staff

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Implement Merge Sort and Return a Sorted Array Implement `mergeSort(values)` using merge sort and return all input integers in nondecreasing order. Do not call a built-in sorting function. Your implementation should divide the input until each subproblem has at most one element, merge sorted subproblems, and handle repeated and negative values correctly. ## Constraints - `0 <= values.length <= 200,000` - `-10^9 <= values[i] <= 10^9` - The returned array must contain exactly the same multiset of values as the input. - The intended time complexity is `O(n log n)`. ## Example 1 ```text Input: values = [5, 2, 4, 2, -1] Output: [-1, 2, 2, 4, 5] ``` Both copies of `2` remain in the result. ## Example 2 ```text Input: values = [] Output: [] ``` An empty input is already sorted.

Overview: Implement merge sort from first principles and return integers in nondecreasing order without a built-in sort. The exercise covers empty input, duplicates, negative values, multiset preservation, divide-and-merge structure, and the expected logarithmic recursion depth.

Read the full Salesforce Member of Technical Staff interview experience this question came from

Implement mergeSort(values) with merge sort and return every input integer in nondecreasing order. Do not call a built-in sorting function. Repeated and negative values must remain, and the result must contain exactly the input multiset.

Constraints

  • 0 <= values.length <= 200,000
  • -10^9 <= values[i] <= 10^9
  • The returned array contains exactly the same multiset as values.
  • A built-in sorting function may not be called.

Examples

Input: ([],)

Expected Output: []

Explanation: The empty source example is already sorted.

Input: ([7],)

Expected Output: [7]

Explanation: A one-element subproblem needs no merge.

Hints

  1. Merge two sorted ranges with one pointer in each range.
  2. An iterative run width of 1, 2, 4, and so on avoids recursion while remaining merge sort.

Loading coding console...

Show the approach

Approach

Treat each single element as an initially sorted run. On every bottom-up pass, merge adjacent runs of the current width into a separate buffer by repeatedly taking the smaller front value, then copy the unconsumed suffix of either run. Swap the source and destination buffers and double the run width. After the first width that covers the whole input, the active source buffer is the sorted result. This is merge sort without a built-in sorting call and naturally preserves duplicates.

Time complexity:
O(n log n) for n input values.
Space complexity:
O(n) auxiliary space for the copied input and merge buffer.