Merge Sorted

While similar in name to the Merge Sort, the Merge Sorted is a bit of a special case type of sort, and shares none of the same methodology. 

In it, you take two, or more sources, which are already sorted, and you merge them together. As you merge them together, you determine from which list, or array, the next element should come from. The key, which is easy to miss, is that all of the sources must already be sorted on their own.

In the simplest case, consider the following pseudo where there are two arrays being merged together to form one sorted array. Remember, the individual arrays are already sorted.

While list1 and list2 is not empty
	If list1.nextElement > list2.nextElement then
		Merged.append( list2.nextElement )
	Else
		Merged.append( list1.nextElement )
	End if
End While
While list1 is not empty 
	// now add the rest of the elements from the first list if there are any
	Merged.append( list1.nextElement )
End While
While list2 is not empty 
	// now add the rest of the elements from the second list if there are any
	Merged.append( list2.nextElement )
End While

Notice that once one of the arrays is empty, you have to still work on adding the rest of the remaining array. Failing to do so will cause your data to be incomplete.

Merge Sorted was originally found on Access 2 Learn