How do you merge two sorted lists into a sorted one? This is the task of the merge() function, which is found at the end of the pseudocode shown in the preceding section. This process is shown in Figure 2.4. Merging two sorted lists is an easier task than sorting from scratch.

This is similar to the intersection problem we saw in Chapter 1, Algorithms and Complexities.

We can merge in linear time utilizing just two pointers and an empty array as shown in the following diagram:

The pseudocode for the merging is shown in the following code snippet. In this code, the copyArray() function simply takes in a source array as a first argument and copies it to the target array, that is, the second argument. It makes use of the start variable as a pointer, indicating where to place the first element of the source array onto the target one. The pseudocode is as follows:

merge(array, start, middle, end)
  i = start
  j = middle + 1
  arrayTemp = initArrayOfSize(end - start + 1)
  for (k = 0 until end-start)
    if (i <= middle && (j > end || array[i] <= array[j]))
      arrayTemp[k] = array[i]
      i++
    else
      arrayTemp[k] = array[j]
      j++
  copyArray(arrayTemp, array, start)  

In the merging part of the merge sort, we create a temporary array which is of size equal to the size of two array parts together. We then do a single pass on this array, filling the temporary array one item at a time by picking the smallest item between the two input lists (represented by the start, middle, and end pointers). After picking an item from one of the lists, we advance the pointer of that list and repeat until the merge is complete.

Merge sort is theoretically one of the fastest sorting algorithms. The drawback of its speed is that it consumes a bit more memory, although some implementations exist that perform the merge step in place to save memory.

For comparison, we present multiple sorting techniques with their runtime and memory performances in the following table: