Merge Sorted Arrays

An interactive, step-by-step visualisation of Merge Sorted Arrays.

Category: Two Pointers
Time complexity: O(n + m)
Space complexity: O(1)

Pseudocode

i, j, k = end of real A, end of B, end of padded A
while j >= 0:
  place the larger of a[i], b[j] at k; decrement

Reference implementation

i, j, k = m-1, n-1, m+n-1
while j &gt;= 0:
    if i &gt;= 0 and a[i] &gt; b[j]:
        a[k] = a[i]; i -= 1
    else:
        a[k] = b[j]; j -= 1
    k -= 1

Open the interactive Merge Sorted Arrays visualisation →