Do I have to combine the lists before or after sorting?


#1

Question

In the context of this code challenge, do I have to combine the lists before or after sorting?

Answer

You are free to combine the lists either before or after you perform a sort. However, depending on which order you perform the sort and combine steps, it will affect how your code must be implemented.

Say that you choose to sort each list first, before combining them. If you sort them first, then adding the lists together as is can result in an unsorted list. For example,

list = [1, 3, 5] + [2, 4, 6] 
# [1, 3, 5, 2, 4, 6]

In order to have the combined list sorted as well, you can implement a way to merge the two lists, so that each element is added to the combined list in the correct order.

To do this, you can have pointers in the front of each sorted list, and constantly compare the current element that both pointers are at. Whichever element is less can be added to the combined list, and then the pointer of the lesser element can move to the right by one index to the next element.

This way of merging two sorted lists is part of the merge sort algorithm, which you are free to check out and see how it works.