On Mon, Jan 04, 2016 at 12:34:57PM -0500, Pooja Bhalode wrote: > Hi, I wanted to check if this program can be used to merge the lists > together and sort them. This seems to work, but i wanted to check if there > are drawbacks in writing it in this manner. > > My solution: > > def linear_merge(list1, list2): > for num in list2: > list1.append(num) > list1.sort() > return list1
One small change: def linear_merge(list1, list2): list1.extend(list2) list1.sort() return list1 is easier to write and faster. For use in an actual program, this method is perfectly acceptible, although this version modifies the first list in place rather than make a copy. If you want a copy: def linear_merge(list1, list2): result = list1[:] result.extend(list2) result.sort() return result Or more compact, but not quite as efficient: def linear_merge(list1, list2): return sorted(list1 + list2) You should play around with these and see if you can understand how they differ. For a practice exercise, none of the above might be acceptible. Usually, when people talk about "merging" lists, they mean to avoid calling sort. Sorting, on average, takes time proportional to N*log N, where N is the number of items. So if you have 1000 items, sorting will take time proportional to 1000*(log 1000), or 3000. But "merging" should take time proportional to just N, or 1000. So in theory, merging may be faster. So for practice exercises, it is often expected that you do not just add the two lists together and sort as we did above. Let's look at their code: > def linear_merge(list1, list2): > result = [] > # Look at the two lists so long as both are non-empty. > # Take whichever element [0] is smaller. > while len(list1) and len(list2): > if list1[0] < list2[0]: > result.append(list1.pop(0)) > else: > result.append(list2.pop(0)) > # Now tack on what's left > result.extend(list1) > result.extend(list2) > return result As you can see, there is no call to sort. (This does assume that each list is itself sorted, but that is normal for this type of question.) So the function starts with a new, empty, list and then it keeps looking at the two lists. It looks at the first item from each list, picks the smaller, and moves it to the new list. When one or the other list has run out of items, the function then does a quick copy of the rest of the items from the other. However, while this might technically be a merge, it is actually *very* inefficient. It will actually take time proportional to N**2, due to the list.pop calls. Each time you pop an item from the *beginning* of a list, all the other items have to be moved back one space. So if you have 10 items in the list, and remove the first one, the remaining 9 have to move; then you remove the first, now the remaining 8 have to move; and so on. If you don't understand this, don't worry about it too much, the important thing is that the answer given will perform very slowly for large lists with millions of items. Here's a better version: def merge(lista, listb): # Assumes that both lista and listb are already sorted. new = [] i = 0 # Index of an item in lista j = 0 # Index of an item in listb while i < len(lista) and j < len(listb): if lista[i] < listb[j]: new.append(lista[i]) i += 1 else: new.append(listb[j]) j += 1 new.extend(lista[i:]) new.extend(listb[j:]) return new -- Steve _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor