How to merge two sorted PHP arrays without array_merge() or sort()

I’ve had this question come up a few times in the past on interviews, how would you merge two sorted arrays and keep their sort order intact? The easy / PHP answer is to simply use array_merge() and then sort() the resulting array. Technically this works but the whole point behind the question is to see if you can work through the logic itself.

Someone recently gave me a great analogy for merging two sorted arrays. They said, think of it like you have 2 decks of cards, how would you manage that? With two decks of cards, the first thing to do would be to flip over one card from each stack. Once you have a card from each stack, you an compare the two cards and determine which one is smaller. That smaller card can then be placed into a new deck and another card can be flipped over. Continue the process until both decks are exhausted.

Here’s how the code would look:

// Sets up our arrays
$array1 = [1, 3, 5, 7, 9];
$array2 = [2, 4, 6, 8, 10];
$array3 = [];

// Determines how many items we have in each array
$array1_count = count($array1);
$array2_count = count($array2);

// While we still have at least one item in one of the arrays
while ($array1_count || $array2_count)
{
    $array1_empty = $array1 == [];
    $array2_empty = $array2 == [];

    if (!$array1_empty && !$array2_empty)
    {
        if (current($array1) < current($array2))
        {
            $array3[] = array_shift($array1);
            $array1_count--;
        }
        else
        {
            $array3[] = array_shift($array2);
            $array2_count--;
        }
    }
    elseif (!$array1_empty)
    {
        $array3[] = array_shift($array1);
        $array1_count--;
    }
    elseif (!$array2_empty)
    {
        $array3[] = array_shift($array2);
        $array2_count--;
    }
}

It’s not that pretty, but it gets the job done. Got a more elegant solution without using array_merge() and/or sort()? Feel free to share it below in the comments!