Skip to main content
Back to ChallengesExternal Sorting ConceptsHard 50 min

External Sorting Concepts

External sorting handles massive amounts of data that don't fit in memory. To simulate this, you are given an array of k fully sorted 'chunks' (arrays). You must merge them into a single sorted array. (This is conceptually equivalent to merging chunks from disk).

Merge the k sorted arrays into one sorted array.

Examples

Input: chunks = [[1,4,5], [1,3,4], [2,6]]
Output: [1,1,2,3,4,4,5,6]
Merging the sorted chunks gives the final sorted list.

Constraints

  • • 1 <= chunks.length <= 10^4
  • • 1 <= chunks[i].length <= 500
  • • -10^4 <= chunks[i][j] <= 10^4

Complexity Analysis

Time
O(N log k) where N is total elements, k is the number of chunks.
Space
O(N)
storing the merged results.

Test Cases

#1 Merge 3 arrays
Input: chunks = [[1,4,5], [1,3,4], [2,6]]
Expected: [1,1,2,3,4,4,5,6]
#2 Single array
Input: chunks = [[1]]
Expected: [1]
JavaScript
Output
Click "Run Code" to see output here...