Coding questions · Apple

Sort and merge string lists by length

This question evaluates understanding of sorting algorithms, stability, merging strategies, and time/space complexity analysis when ordering strings by length, and is categorized under Coding & Algorithms.

Given two unsorted lists of strings, return a single list sorted by ascending string length. Specify your tie-breaking rule for equal-length strings (e.g., preserve original relative order for stability). Analyze time and space complexity and whether your sort is stable. Follow-up: If each input list is already individually sorted by length with the same tie-breaker, design and implement an efficient merge to produce a globally length-sorted list. Discuss in-place versus extra-memory approaches and their complexities.

Sort and Merge String Lists by Length

Return all strings sorted by ascending length. Ties preserve original relative order, treating list1 followed by list2 as the original order. If already_sorted=True, assume each input is already length-sorted with the same tie rule and merge them linearly.

Constraints

Input strings may have equal lengths
When already_sorted=True both lists are individually sorted by length

Examples

Example 1

Input: (['pear', 'a', 'plum'], ['bb', 'apple'], False)
Output: ['a', 'bb', 'pear', 'plum', 'apple']

Example 2

Input: (['a', 'bb', 'cccc'], ['d', 'eee'], True)
Output: ['a', 'd', 'bb', 'eee', 'cccc']

Hints

Stable sorting solves the unsorted case.
The follow-up is the merge step from merge sort.