Write a function to merge two sorted lists into one sorted list. Optimize for minimal space usage.

Overview

Merging two sorted lists is a fundamental algorithm that combines two already-sorted arrays into a single sorted array. This is the core operation in Merge Sort and appears frequently in real-world scenarios.

Problem:

• Input:
  textCopy

  [1, 3, 5]

  and
  textCopy

  [2, 4, 6]

• Output:
  textCopy

  [1, 2, 3, 4, 5, 6]

Key characteristics:

• Both input arrays are already sorted
• Output must maintain sorted order
• Should be more efficient than concatenating and sorting

Real-world applications:

• Merging sorted logs from multiple servers
• Combining sorted database query results
• External sorting for large files
• Merge sort algorithm
• Real-time data stream merging

Algorithm Explanation

Two-Pointer Technique:

1. Use two pointers, one for each array
2. Compare elements at both pointers
3. Add smaller element to result
4. Move the pointer of the array from which element was taken
5. When one array is exhausted, append remaining elements from other

Visual Example:

textCopy
Array 1: [1, 3, 5]     Array 2: [2, 4, 6]
         ↑                       ↑
         i=0                     j=0

Step 1: 1 < 2 → add 1, i++     Result: [1]
Step 2: 3 > 2 → add 2, j++     Result: [1, 2]
Step 3: 3 < 4 → add 3, i++     Result: [1, 2, 3]
Step 4: 5 > 4 → add 4, j++     Result: [1, 2, 3, 4]
Step 5: 5 < 6 → add 5, i++     Result: [1, 2, 3, 4, 5]
Step 6: arr1 done, add rest    Result: [1, 2, 3, 4, 5, 6]

Approach 1: Two-Pointer Merge (Optimal)

Most efficient approach using two pointers.

dartCopy
List<int> mergeSorted(List<int> arr1, List<int> arr2) {
  List<int> result = [];
  int i = 0;  // Pointer for arr1
  int j = 0;  // Pointer for arr2

  // Compare and merge while both have elements
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.add(arr1[i]);
      i++;
    } else {
      result.add(arr2[j]);
      j++;
    }
  }

  // Add remaining elements from arr1
  while (i < arr1.length) {
    result.add(arr1[i]);
    i++;
  }

  // Add remaining elements from arr2
  while (j < arr2.length) {
    result.add(arr2[j]);
    j++;
  }

  return result;
}

void main() {
  List<int> arr1 = [1, 3, 5, 7];
  List<int> arr2 = [2, 4, 6, 8];

  print(mergeSorted(arr1, arr2));
  // Output: [1, 2, 3, 4, 5, 6, 7, 8]

  List<int> arr3 = [1, 2, 3];
  List<int> arr4 = [4, 5, 6];
  print(mergeSorted(arr3, arr4));
  // Output: [1, 2, 3, 4, 5, 6]
}

Time Complexity: O(n + m) where n, m are array lengths Space Complexity: O(n + m) for result array

Advantages:

• Single pass through both arrays
• No sorting needed
• Optimal time complexity

Approach 2: Using addAll with Sublist

More concise but same complexity.

dartCopy
List<int> mergeSortedConcise(List<int> arr1, List<int> arr2) {
  List<int> result = [];
  int i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.add(arr1[i++]);
    } else {
      result.add(arr2[j++]);
    }
  }

  // Add remaining elements (only one of these will execute)
  result.addAll(arr1.sublist(i));
  result.addAll(arr2.sublist(j));

  return result;
}

void main() {
  print(mergeSortedConcise([1, 3, 5], [2, 4, 6]));
  // Output: [1, 2, 3, 4, 5, 6]
}

Time: O(n + m), Space: O(n + m)

Advantage: Cleaner code with sublist

Approach 3: Concatenate and Sort (Simple but Inefficient)

The naive approach - works but not optimal.

dartCopy
List<int> mergeSortedNaive(List<int> arr1, List<int> arr2) {
  List<int> result = [...arr1, ...arr2];
  result.sort();
  return result;
}

void main() {
  print(mergeSortedNaive([3, 5, 7], [2, 4, 6]));
  // Output: [2, 3, 4, 5, 6, 7]
}

Time Complexity: O((n + m) log(n + m)) - sorting dominates Space Complexity: O(n + m)

When to use:

• Quick prototypes
• When arrays are very small
• When code simplicity > performance

Why avoid in interviews:

• Doesn't leverage sorted property
• Much slower than two-pointer approach

Approach 4: In-Place Merge (Space Optimized for arr1)

Merge into first array if it has enough capacity.

dartCopy
void mergeInPlace(List<int> arr1, int m, List<int> arr2, int n) {
  // Merge from back to front to avoid overwriting
  int i = m - 1;      // Last element of arr1's data
  int j = n - 1;      // Last element of arr2
  int k = m + n - 1;  // Last position in arr1

  while (i >= 0 && j >= 0) {
    if (arr1[i] > arr2[j]) {
      arr1[k--] = arr1[i--];
    } else {
      arr1[k--] = arr2[j--];
    }
  }

  // Copy remaining from arr2 (if arr1 done first)
  while (j >= 0) {
    arr1[k--] = arr2[j--];
  }
  // No need to copy remaining from arr1 - already in place
}

void main() {
  // arr1 has space for m+n elements
  List<int> arr1 = [1, 3, 5, 0, 0, 0];
  List<int> arr2 = [2, 4, 6];

  mergeInPlace(arr1, 3, arr2, 3);
  print(arr1);  // [1, 2, 3, 4, 5, 6]
}

Time: O(n + m), Space: O(1) - modifies arr1 in place!

Use case: LeetCode #88 "Merge Sorted Array"

Approach 5: Generic Merge with Comparator

Support any comparable type.

dartCopy
List<T> mergeSortedGeneric<T>(
  List<T> arr1,
  List<T> arr2,
  int Function(T a, T b) compare,
) {
  List<T> result = [];
  int i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (compare(arr1[i], arr2[j]) <= 0) {
      result.add(arr1[i++]);
    } else {
      result.add(arr2[j++]);
    }
  }

  result.addAll(arr1.sublist(i));
  result.addAll(arr2.sublist(j));

  return result;
}

void main() {
  // Merge integers
  var ints = mergeSortedGeneric(
    [1, 3, 5],
    [2, 4, 6],
    (a, b) => a.compareTo(b),
  );
  print(ints);  // [1, 2, 3, 4, 5, 6]

  // Merge strings
  var strings = mergeSortedGeneric(
    ['apple', 'cherry'],
    ['banana', 'date'],
    (a, b) => a.compareTo(b),
  );
  print(strings);  // [apple, banana, cherry, date]
}

Complete Solution Class

Production-ready implementation with all features.

dartCopy
class MergeSorted {
  /// Standard two-pointer merge
  static List<int> merge(List<int> arr1, List<int> arr2) {
    List<int> result = [];
    int i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
      if (arr1[i] <= arr2[j]) {
        result.add(arr1[i++]);
      } else {
        result.add(arr2[j++]);
      }
    }

    result.addAll(arr1.sublist(i));
    result.addAll(arr2.sublist(j));

    return result;
  }

  /// In-place merge (arr1 must have capacity for arr1 + arr2)
  static void mergeInPlace(List<int> arr1, int m, List<int> arr2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;

    while (i >= 0 && j >= 0) {
      if (arr1[i] > arr2[j]) {
        arr1[k--] = arr1[i--];
      } else {
        arr1[k--] = arr2[j--];
      }
    }

    while (j >= 0) {
      arr1[k--] = arr2[j--];
    }
  }

  /// Generic merge with comparator
  static List<T> mergeGeneric<T>(
    List<T> arr1,
    List<T> arr2,
    int Function(T a, T b) compare,
  ) {
    List<T> result = [];
    int i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
      if (compare(arr1[i], arr2[j]) <= 0) {
        result.add(arr1[i++]);
      } else {
        result.add(arr2[j++]);
      }
    }

    result.addAll(arr1.sublist(i));
    result.addAll(arr2.sublist(j));

    return result;
  }

  /// Merge with duplicate handling
  static List<int> mergeUnique(List<int> arr1, List<int> arr2) {
    List<int> result = [];
    int i = 0, j = 0;
    int? last;

    while (i < arr1.length && j < arr2.length) {
      int val;
      if (arr1[i] <= arr2[j]) {
        val = arr1[i++];
      } else {
        val = arr2[j++];
      }

      if (val != last) {
        result.add(val);
        last = val;
      }
    }

    while (i < arr1.length) {
      if (arr1[i] != last) {
        result.add(arr1[i]);
        last = arr1[i];
      }
      i++;
    }

    while (j < arr2.length) {
      if (arr2[j] != last) {
        result.add(arr2[j]);
        last = arr2[j];
      }
      j++;
    }

    return result;
  }

  /// Merge multiple sorted lists
  static List<int> mergeMultiple(List<List<int>> arrays) {
    if (arrays.isEmpty) return [];

    List<int> result = arrays[0];
    for (int i = 1; i < arrays.length; i++) {
      result = merge(result, arrays[i]);
    }

    return result;
  }
}

Comparison Table

For interviews: Use Two-Pointer or In-Place (if asked about space)

Visualization Example

Merging

[1, 4, 7]

[2, 3, 8]

dartCopy
void visualize() {
  List<int> arr1 = [1, 4, 7];
  List<int> arr2 = [2, 3, 8];
  List<int> result = [];

  int i = 0, j = 0;
  int step = 1;

  while (i < arr1.length && j < arr2.length) {
    print('Step $step:');
    print('  arr1[$i]=${arr1[i]}, arr2[$j]=${arr2[j]}');

    if (arr1[i] <= arr2[j]) {
      result.add(arr1[i]);
      print('  → Add ${arr1[i]} from arr1');
      i++;
    } else {
      result.add(arr2[j]);
      print('  → Add ${arr2[j]} from arr2');
      j++;
    }

    print('  Result so far: $result
');
    step++;
  }

  result.addAll(arr1.sublist(i));
  result.addAll(arr2.sublist(j));
  print('Final: $result');
}

// Output:
// Step 1:
//   arr1[0]=1, arr2[0]=2
//   → Add 1 from arr1
//   Result so far: [1]
//
// Step 2:
//   arr1[1]=4, arr2[0]=2
//   → Add 2 from arr2
//   Result so far: [1, 2]
// ...

Edge Cases

dartCopy
void testEdgeCases() {
  // Both empty
  assert(MergeSorted.merge([], []) == []);

  // One empty
  assert(MergeSorted.merge([1, 2], []) == [1, 2]);
  assert(MergeSorted.merge([], [3, 4]) == [3, 4]);

  // No overlap
  assert(MergeSorted.merge([1, 2], [3, 4]) == [1, 2, 3, 4]);
  assert(MergeSorted.merge([3, 4], [1, 2]) == [1, 2, 3, 4]);

  // Complete overlap
  assert(MergeSorted.merge([1, 2, 3], [1, 2, 3]) == [1, 1, 2, 2, 3, 3]);

  // Interleaved
  assert(MergeSorted.merge([1, 3, 5], [2, 4, 6]) == [1, 2, 3, 4, 5, 6]);

  // Different sizes
  assert(MergeSorted.merge([1], [2, 3, 4, 5]) == [1, 2, 3, 4, 5]);

  // Duplicates
  assert(MergeSorted.merge([1, 1, 2], [1, 2, 2]) == [1, 1, 1, 2, 2, 2]);
}

Best Practices

1. Always Use Two-Pointer for Sorted Arrays

dartCopy
// ✅ Good - O(n + m)
List<int> merged = MergeSorted.merge(arr1, arr2);

// ❌ Bad - O((n+m) log(n+m))
List<int> merged = [...arr1, ...arr2]..sort();

2. Handle Edge Cases

dartCopy
// ✅ Validate inputs
List<int> mergeSafe(List<int>? arr1, List<int>? arr2) {
  if (arr1 == null || arr1.isEmpty) return arr2 ?? [];
  if (arr2 == null || arr2.isEmpty) return arr1;
  return MergeSorted.merge(arr1, arr2);
}

3. Use In-Place When Space is Critical

dartCopy
// ✅ Space-optimized when arr1 has capacity
void mergeToFirst(List<int> arr1, int m, List<int> arr2, int n) {
  MergeSorted.mergeInPlace(arr1, m, arr2, n);
}

4. Consider Merge for K-way Merge

dartCopy
// Merge multiple sorted arrays
List<List<int>> sortedArrays = [
  [1, 4, 7],
  [2, 5, 8],
  [3, 6, 9],
];

List<int> result = MergeSorted.mergeMultiple(sortedArrays);

Interview Tips

Common Interview Questions:

Q: "What's the time complexity?"

• Two-pointer: O(n + m) - optimal
• Concatenate+sort: O((n+m) log(n+m)) - not optimal

Q: "Can you do it in O(1) space?"

• Yes, if arr1 has capacity (in-place merge)
• Merge from back to front

Q: "How is this used in merge sort?"

• Merge sort divides array, then uses this to merge
• This is the "merge" in "merge sort"

Q: "What if one array is much larger?"

• Still O(n + m)
• Consider binary search insertion if ratio is huge

Follow-up Questions:

• "Merge k sorted arrays?" → Min heap or pairwise merging
• "Remove duplicates while merging?" → Track last added value
• "Merge linked lists?" → Same logic, different data structure
• "Descending order?" → Reverse comparison

What to Explain:

1. Why two-pointer is optimal for sorted arrays
2. Why concatenate+sort wastes the sorted property
3. How in-place merge works from back to front
4. Connection to merge sort algorithm

Red Flags to Avoid:

• Using concatenate+sort in production ❌
• Not handling empty arrays ❌
• Comparing with > instead of >= (unstable) ❌
• Forgetting to add remaining elements ❌

Pro Tips:

• Mention this is the core of Merge Sort
• Draw two arrays and show pointer movement
• Explain why merging is O(n+m) not O(n*m)
• Compare with real-world: merging sorted logs

Resources

• Merge Sort - Wikipedia
• Two Pointers Technique
• Merge Sorted Array - LeetCode