Odtnhj

I'm looking for a way to merge 3 sorted lists of ascending order without using any built-in functions or recursion.
For example:

merge([1,4],[1,5,6],[3,7,9]) produces [1,1,3,4,5,6,7,9]

I have the following done so far but it does not produce the expected above result.

def merge(list1, list2, list3):
 results = 
 while len(list1) and len(list2) and len(list3):
 if (list1[0] < list2[0]) and (list1[0] < list3[0]):
 results.append(list1.pop(0))
 elif (list2[0] < list1[0]) and (list2[0] < list3[0]):
 results.append(list2.pop(0))
 elif (list3[0] < list1[0]) and (list3[0] < list2[0]):
 results.append(list3.pop(0))
 results.extend(list1)
 results.extend(list2)
 results.extend(list3)
 return results

Your use of < rather than <= is causing you problems. In the case where you have identical data points, it can easily lead to none of the if statements firing. Specifically, take your first data point from each list, 1/1/3, and use them in the conditions for your three if statements:

(1 < 1) and (1 < 3): no, fails first part
(1 < 1) and (1 < 3): no, fails first part
(3 < 1) and (3 < 1): no, fails both parts

That causes an infinite loop since no action is being taken to modify the lists.

In any case, I think you're overly complicating things with a three-way merge when you can just do it as a couple of two-way merges:

def merge2(list1, list2):
 result = 
 idx1 = 0
 idx2 = 0

 # Get lowest while both lists are active.

 while idx1 < len(list1) and idx2 < len(list2):
 if list1[idx1] <= list2[idx2]:
 result.append(list1[idx1])
 idx1 += 1
 else:
 result.append(list2[idx2])
 idx2 += 1

 # Get remainder of each list (only one will be active here).

 while idx1 < len(list1):
 result.append(list1[idx1])
 idx1 += 1

 while idx2 < len(list2):
 result.append(list2[idx2])
 idx2 += 1

 return result

def merge(list1, list2, list3):
 # Three-way is two two-ways.

 return merge2(merge2(list1, list2), list3)

print(merge([1,4],[1,5,6],[3,7,9]))

This is slightly less efficient than a three-way but won't really make a difference unless you use truly large data sets (and, in my opinion, doing it this way results in a much "cleaner" program).

Of course the smart way to do this would be to use the actual facilities of the language. Even though you've stated you don't want to do that (and I'm not sure why that would be the case, other than maybe an artificial restriction for classwork), the Pythonic way would be:

def merge(list1, list2, list3):
 allitems = [item for sublist in [list1, list2, list3] for item in sublist]
 allitems.sort()
 return allitems

And, in fact, you could make it handle arbitrary list quantities by providing a list of lists in the call, rather than a fixed number of lists:

def merge(listOfLists):
 allitems = [item for sublist in listOfLists for item in sublist]
 allitems.sort()
 return allitems

print(merge([[1,4],[1,5,6],[3,7,9]])) # Three lists, but any number will work.

Or use non-builtin sorting way:

def merge(*l):
 l=[x for i in l for x in i]
 newl = 
 while l:
 mi = l[0]
 for x in l: 
 if x < mi:
 mi = x
 newl.append(mi)
 l.remove(mi) 

 return newl

Now:

print(merge([1,4],[1,5,6],[3,7,9]))

Is:

[1, 1, 3, 4, 5, 6, 7, 9]

Whithout any builtin function and so:

a quite simple form:

def merge(*lists_in):
 list_in = 
 for l in lists_in:
 list_in += l

 i = 0
 while True:
 if i == list_in.__len__() -1:
 break
 if list_in[i] > list_in[i+1]:
 temp = list_in[i]
 list_in[i] = list_in[i+1]
 list_in[i+1] = temp
 i = 0
 else:
 i += 1

return list_in

Testing it:

list1 = [1,4] 
list2 = [1,5,6]
list3 = [3,7,9]

print(merge(list1, list2, list3))

Out:

[1, 1, 3, 4, 5, 6, 7, 9]