Merge sorted lists L1 and L2 into a new list - merge function

For each pair of items L1[i1] and L2[i2], copy the smaller into newL.
Move i1 or i2 up, until one of the two lists is empty.
Copy the rest of elements to newL.

Merge Sort

  1. Break each item to a list and put them into a large list - workspace
  2. Merge every two lists in workspace until no more to be merged.
  3. The last element of workspace is the final sorted list.

Example