Combining two sorted lists in Python

Question

I have two lists of objects  Each list is already sorted by a property of the object that is of the datetime type  I would like to combine the two lists into one sorted list  Is the best way just to do a sort or is there a smarter way to do this in Python

User · Answer

Use the  merge  step of merge sort  it runs in O n  time   From wikipedia  pseudo-code    function merge left right      var list result     while length left   gt  0 and length right   gt  0         if first left    first right              append first left  to result             left   rest left          else             append first right  to result             right   rest right      end while     while length left   gt  0          append left to result     while length right   gt  0          append right to result     return result

User · Answer

This is simple merging of two sorted lists  Take a look at the sample code below which merges two sorted lists of integers      usr bin env python    merge py -- Merge two sorted lists - - Python - -    Time-stamp   2009-01-21 14 02 57 ghoseb   l1    1  3  4  7  l2    0  2  5  6  8  9   def merge sorted lists l1  l2          Merge sort two sorted lists      Arguments      -  l1   First sorted list     -  l2   Second sorted list             sorted list             Copy both the args to make sure the original lists are not       modified     l1   l1        l2   l2         while  l1 and l2           if  l1 0   lt   l2 0      Compare both heads             item   l1 pop 0    Pop from the head             sorted list append item          else              item   l2 pop 0              sorted list append item         Add the remaining of the lists     sorted list extend l1 if l1 else l2       return sorted list  if   name         main         print merge sorted lists l1  l2    This should work fine with datetime objects  Hope this helps

User · Answer

def compareDate obj1  obj2       if obj1 getDate    lt  obj2 getDate            return -1     elif obj1 getDate    gt  obj2 getDate            return 1     else          return 0    list   list1   list2 list sort compareDate    Will sort the list in place  Define your own function for comparing two objects  and pass that function into the built in sort function   Do NOT use bubble sort  it has horrible performance

User · Answer

People seem to be over complicating this   Just combine the two lists  then sort them    gt  gt  gt  l1    1  3  4  7   gt  gt  gt  l2    0  2  5  6  8  9   gt  gt  gt  l1 extend l2   gt  gt  gt  sorted l1   0  1  2  3  4  5  6  7  8  9      or shorter  and without modifying l1     gt  gt  gt  sorted l1   l2   0  1  2  3  4  5  6  7  8  9      easy  Plus  it s using only two built-in functions  so assuming the lists are of a reasonable size  it should be quicker than implementing the sorting merging in a loop  More importantly  the above is much less code  and very readable   If your lists are large  over a few hundred thousand  I would guess   it may be quicker to use an alternative custom sorting method  but there are likely other optimisations to be made first  e g not storing millions of datetime objects   Using the timeit Timer   repeat    which repeats the functions 1000000 times   I loosely benchmarked it against ghoseb s solution  and sorted l1 l2  is substantially quicker   merge sorted lists took     9 7439379692077637  9 8844599723815918  9 552299976348877    sorted l1 l2  took     2 860386848449707  2 7589840888977051  2 7682540416717529

User · Answer

is there a smarter way to do this in Python   This hasn t been mentioned  so I ll go ahead - there is a merge stdlib function in the heapq module of python 2 6   If all you re looking to do is getting things done  this might be a better idea  Of course  if you want to implement your own  the merge of merge-sort is the way to go    gt  gt  gt  list1    1  5  8  10  50   gt  gt  gt  list2    3  4  29  41  45  49   gt  gt  gt  from heapq import merge  gt  gt  gt  list merge list1  list2    1  3  4  5  8  10  29  41  45  49  50    Here s the documentation

User · Answer

Python s sort implementation  timsort  is specifically optimized for lists that contain ordered sections   Plus  it s written in C     http   bugs python org file4451 timsort txt http   en wikipedia org wiki Timsort  As people have mentioned  it may call the comparison function more times by some constant factor  but maybe call it more times in a shorter period in many cases        I would never rely on this  however      Daniel Nadasi   I believe the Python developers are committed to keeping timsort  or at least keeping a sort that s O n  in this case      Generalized sorting  i e  leaving apart radix sorts from limited value domains    cannot be done in less than O n log n  on a serial machine      Barry Kelly   Right  sorting in the general case can t be faster than that   But since O   is an upper bound  timsort being O n log n  on arbitrary input doesn t contradict its being O n  given sorted L1    sorted L2

User · Answer

import random      n int input  Enter size of table 1      size of list 1     m int input  Enter size of table 2       size of list 2     tb1  random randrange 1 101 1  for   in range n     filling the list with random     tb2  random randrange 1 101 1  for   in range m     numbers between 1 and 100     tb1 sort     sort the list 1      tb2 sort      sort the list 2     fus       creat an empty list     print tb1     print the list 1     print  ------------------------------------        print tb2     print the list 2     print  ------------------------------------        i 0 j 0     varialbles to cross the list     while i lt n and j lt m           if tb1 i  lt tb2 j                fus append tb1 i                 i  1          else              fus append tb2 j                j  1       if i lt n           fus  tb1 i n       if j lt m           fus  tb2 j m        print fus        this code is used to merge two sorted lists in one sorted list  FUS  without    sorting the  FUS

User · Answer

Have used merge step of the merge sort  But I have used generators   Time complexity O n   def merge lst1 lst2       len1 len lst1      len2 len lst2      i j 0 0     while i lt len1 and j lt len2           if lst1 i  lt lst2 j                    yield lst1 i                  i  1         else                  yield lst2 j                  j  1     if i  len1           while j lt len2                   yield lst2 j                  j  1     elif j  len2           while i lt len1                   yield lst1 i                  i  1 l1  1 3 5 7  l2  2 4 6 8 9  mergelst  val for val in merge l1 l2   print  mergelst

User · Answer

from datetime import datetime from itertools import chain from operator import attrgetter  class DT      def   init   self  dt           self dt   dt  list1    DT datetime 2008  12  5  2             DT datetime 2009  1  1  13             DT datetime 2009  1  3  5     list2    DT datetime 2008  12  31  23             DT datetime 2009  1  2  12             DT datetime 2009  1  4  15     list3   sorted chain list1  list2   key attrgetter  dt    for item in list3      print item dt   The output   2008-12-05 02 00 00 2008-12-31 23 00 00 2009-01-01 13 00 00 2009-01-02 12 00 00 2009-01-03 05 00 00 2009-01-04 15 00 00   I bet this is faster than any of the fancy pure-Python merge algorithms  even for large data  Python 2 6 s heapq merge is a whole another story

User · Answer

def compareDate obj1  obj2       if obj1 getDate    lt  obj2 getDate            return -1     elif obj1 getDate    gt  obj2 getDate            return 1     else          return 0    list   list1   list2 list sort compareDate    Will sort the list in place  Define your own function for comparing two objects  and pass that function into the built in sort function   Do NOT use bubble sort  it has horrible performance

User · Answer

This code has time complexity O n  and can merge lists of any data type  given a quantifying function as the parameter func  It produces a new merged list and does not modify either of the lists passed as arguments   def merge sorted lists listA listB func       merged   list       iA   0     iB   0     while True          hasA   iA  lt  len listA          hasB   iB  lt  len listB          if not hasA and not hasB              break         valA   None if not hasA else listA iA          valB   None if not hasB else listB iB          a   None if not hasA else func valA          b   None if not hasB else func valB          if  not hasB or a lt b  and hasA              merged append valA              iA    1         elif hasB              merged append valB              iB    1     return merged

User · Answer

This is my solution in linear time without editing l1 and l2   def merge l1  l2     m  m2   len l1   len l2    newList        l  r   0  0   while l  lt  m and r  lt  m2      if l1 l   lt  l2 r         newList append l1 l         l    1     else        newList append l2 r         r    1   return newList   l1 l     l2 r

User · Answer

People seem to be over complicating this   Just combine the two lists  then sort them    gt  gt  gt  l1    1  3  4  7   gt  gt  gt  l2    0  2  5  6  8  9   gt  gt  gt  l1 extend l2   gt  gt  gt  sorted l1   0  1  2  3  4  5  6  7  8  9      or shorter  and without modifying l1     gt  gt  gt  sorted l1   l2   0  1  2  3  4  5  6  7  8  9      easy  Plus  it s using only two built-in functions  so assuming the lists are of a reasonable size  it should be quicker than implementing the sorting merging in a loop  More importantly  the above is much less code  and very readable   If your lists are large  over a few hundred thousand  I would guess   it may be quicker to use an alternative custom sorting method  but there are likely other optimisations to be made first  e g not storing millions of datetime objects   Using the timeit Timer   repeat    which repeats the functions 1000000 times   I loosely benchmarked it against ghoseb s solution  and sorted l1 l2  is substantially quicker   merge sorted lists took     9 7439379692077637  9 8844599723815918  9 552299976348877    sorted l1 l2  took     2 860386848449707  2 7589840888977051  2 7682540416717529

User · Answer

This is simply merging  Treat each list as if it were a stack  and continuously pop the smaller of the two stack heads  adding the item to the result list  until one of the stacks is empty  Then add all remaining items to the resulting list

User · Answer

This is simple merging of two sorted lists  Take a look at the sample code below which merges two sorted lists of integers      usr bin env python    merge py -- Merge two sorted lists - - Python - -    Time-stamp   2009-01-21 14 02 57 ghoseb   l1    1  3  4  7  l2    0  2  5  6  8  9   def merge sorted lists l1  l2          Merge sort two sorted lists      Arguments      -  l1   First sorted list     -  l2   Second sorted list             sorted list             Copy both the args to make sure the original lists are not       modified     l1   l1        l2   l2         while  l1 and l2           if  l1 0   lt   l2 0      Compare both heads             item   l1 pop 0    Pop from the head             sorted list append item          else              item   l2 pop 0              sorted list append item         Add the remaining of the lists     sorted list extend l1 if l1 else l2       return sorted list  if   name         main         print merge sorted lists l1  l2    This should work fine with datetime objects  Hope this helps

User · Answer

This code has time complexity O n  and can merge lists of any data type  given a quantifying function as the parameter func  It produces a new merged list and does not modify either of the lists passed as arguments   def merge sorted lists listA listB func       merged   list       iA   0     iB   0     while True          hasA   iA  lt  len listA          hasB   iB  lt  len listB          if not hasA and not hasB              break         valA   None if not hasA else listA iA          valB   None if not hasB else listB iB          a   None if not hasA else func valA          b   None if not hasB else func valB          if  not hasB or a lt b  and hasA              merged append valA              iA    1         elif hasB              merged append valB              iB    1     return merged

User · Answer

Long story short  unless len l1   l2    1000000 use   L   l1   l2 L sort       Description of the figure and source code can be found here    The figure was generated by the following command     python make-figures py --nsublists 2 --maxn 0x100000 -s merge funcs merge 26 -s merge funcs sort builtin

User · Answer

An implementation of the merging step in Merge Sort that iterates through both lists   def merge lists L1  L2               L1  L2  sorted lists of numbers  one of them could be empty       returns a merged and sorted list of L1 and L2                 When one of them is an empty list  returns the other list     if not L1          return L2     elif not L2          return L1      result          i   0     j   0      for k in range len L1    len L2            if L1 i   lt   L2 j               result append L1 i               if i  lt  len L1  - 1                  i    1             else                  result    L2 j      When the last element in L1 is reached                  break               append the rest of L2 to result          else              result append L2 j               if j  lt  len L2  - 1                  j    1             else                  result    L1 i      When the last element in L2 is reached                  break               append the rest of L1 to result       return result  L1    1  3  5  L2    2  4  6  8  merge lists L1  L2                  Should return  1  2  3  4  5  6  8  merge lists     L1                  Should return  1  3  5    I m still learning about algorithms  please let me know if the code could be improved in any aspect  your feedback is appreciated  thanks

User · Answer

from datetime import datetime from itertools import chain from operator import attrgetter  class DT      def   init   self  dt           self dt   dt  list1    DT datetime 2008  12  5  2             DT datetime 2009  1  1  13             DT datetime 2009  1  3  5     list2    DT datetime 2008  12  31  23             DT datetime 2009  1  2  12             DT datetime 2009  1  4  15     list3   sorted chain list1  list2   key attrgetter  dt    for item in list3      print item dt   The output   2008-12-05 02 00 00 2008-12-31 23 00 00 2009-01-01 13 00 00 2009-01-02 12 00 00 2009-01-03 05 00 00 2009-01-04 15 00 00   I bet this is faster than any of the fancy pure-Python merge algorithms  even for large data  Python 2 6 s heapq merge is a whole another story

User · Answer

There is a slight flaw in ghoseb s solution  making it O n  2   rather than O n   The problem is that this is performing   item   l1 pop 0    With linked lists or deques this would be an O 1  operation  so wouldn t affect complexity  but since python lists are implemented as vectors  this copies the rest of the elements of l1 one space left  an O n  operation   Since this is done each pass through the list  it turns an O n  algorithm into an O n  2  one   This can be corrected by using a method that doesn t alter the source lists  but just keeps track of the current position   I ve tried out benchmarking a corrected algorithm vs a simple sorted l1 l2  as suggested by dbr  def merge l1 l2       if not l1   return list l2      if not l2   return list l1         l2 will contain last element      if l1 -1   gt  l2 -1           l1 l2   l2 l1      it   iter l2      y   it next       result           for x in l1          while y  lt  x              result append y              y   it next           result append x      result append y      result extend it      return result   I ve tested these with lists generated with  l1   sorted  random random   for i in range NITEMS    l2   sorted  random random   for i in range NITEMS      For various sizes of list  I get the following timings  repeating 100 times      items   1000   10000 100000 1000000 merge     0 079  0 798 9 763  109 044  sort      0 020  0 217 5 948  106 882   So in fact  it looks like dbr is right  just using sorted   is preferable unless you re expecting very large lists  though it does have worse algorithmic complexity   The break even point being at around a million items in each source list  2 million total    One advantage of the merge approach though is that it is trivial to rewrite as a generator  which will use substantially less memory  no need for an intermediate list     Edit  I ve retried this with a situation closer to the question - using a list of objects containing a field  date  which is a datetime object  The above algorithm was changed to compare against  date instead  and the sort method was changed to   return sorted l1   l2  key operator attrgetter  date      This does change things a bit   The comparison being more expensive means that the number we perform becomes more important  relative to the constant-time speed of the implementation   This means merge makes up lost ground  surpassing the sort   method at 100 000 items instead   Comparing based on an even more complex object  large strings or lists for instance  would likely shift this balance even more     items   1000   10000 100000  1000000 1  merge     0 161  2 034 23 370  253 68 sort      0 111  1 523 25 223  313 20    1   Note  I actually only did 10 repeats for 1 000 000 items and scaled up accordingly as it was pretty slow

User · Answer

from datetime import datetime from itertools import chain from operator import attrgetter  class DT      def   init   self  dt           self dt   dt  list1    DT datetime 2008  12  5  2             DT datetime 2009  1  1  13             DT datetime 2009  1  3  5     list2    DT datetime 2008  12  31  23             DT datetime 2009  1  2  12             DT datetime 2009  1  4  15     list3   sorted chain list1  list2   key attrgetter  dt    for item in list3      print item dt   The output   2008-12-05 02 00 00 2008-12-31 23 00 00 2009-01-01 13 00 00 2009-01-02 12 00 00 2009-01-03 05 00 00 2009-01-04 15 00 00   I bet this is faster than any of the fancy pure-Python merge algorithms  even for large data  Python 2 6 s heapq merge is a whole another story

User · Answer

If you want to do it in a manner more consistent with learning what goes on in the iteration try this  def merge arrays a  b       l          while len a   gt  0 and len b  gt 0          if a 0   lt  b 0   l append a pop 0               else l append b pop 0        l extend a b      print  l

User · Answer

People seem to be over complicating this   Just combine the two lists  then sort them    gt  gt  gt  l1    1  3  4  7   gt  gt  gt  l2    0  2  5  6  8  9   gt  gt  gt  l1 extend l2   gt  gt  gt  sorted l1   0  1  2  3  4  5  6  7  8  9      or shorter  and without modifying l1     gt  gt  gt  sorted l1   l2   0  1  2  3  4  5  6  7  8  9      easy  Plus  it s using only two built-in functions  so assuming the lists are of a reasonable size  it should be quicker than implementing the sorting merging in a loop  More importantly  the above is much less code  and very readable   If your lists are large  over a few hundred thousand  I would guess   it may be quicker to use an alternative custom sorting method  but there are likely other optimisations to be made first  e g not storing millions of datetime objects   Using the timeit Timer   repeat    which repeats the functions 1000000 times   I loosely benchmarked it against ghoseb s solution  and sorted l1 l2  is substantially quicker   merge sorted lists took     9 7439379692077637  9 8844599723815918  9 552299976348877    sorted l1 l2  took     2 860386848449707  2 7589840888977051  2 7682540416717529

User · Answer

This is simply merging  Treat each list as if it were a stack  and continuously pop the smaller of the two stack heads  adding the item to the result list  until one of the stacks is empty  Then add all remaining items to the resulting list

User · Answer

Use the  merge  step of merge sort  it runs in O n  time   From wikipedia  pseudo-code    function merge left right      var list result     while length left   gt  0 and length right   gt  0         if first left    first right              append first left  to result             left   rest left          else             append first right  to result             right   rest right      end while     while length left   gt  0          append left to result     while length right   gt  0          append right to result     return result

User · Answer

is there a smarter way to do this in Python   This hasn t been mentioned  so I ll go ahead - there is a merge stdlib function in the heapq module of python 2 6   If all you re looking to do is getting things done  this might be a better idea  Of course  if you want to implement your own  the merge of merge-sort is the way to go    gt  gt  gt  list1    1  5  8  10  50   gt  gt  gt  list2    3  4  29  41  45  49   gt  gt  gt  from heapq import merge  gt  gt  gt  list merge list1  list2    1  3  4  5  8  10  29  41  45  49  50    Here s the documentation

User · Answer

def merge sort a b        pa   0     pb   0     result           while pa  lt  len a  and pb  lt  len b           if a pa   lt   b pb               result append a pa               pa    1         else              result append b pb               pb    1      remained   a pa     b pb       result extend remained    return result

User · Answer

This is my solution in linear time without editing l1 and l2   def merge l1  l2     m  m2   len l1   len l2    newList        l  r   0  0   while l  lt  m and r  lt  m2      if l1 l   lt  l2 r         newList append l1 l         l    1     else        newList append l2 r         r    1   return newList   l1 l     l2 r

User · Answer

Have used merge step of the merge sort  But I have used generators   Time complexity O n   def merge lst1 lst2       len1 len lst1      len2 len lst2      i j 0 0     while i lt len1 and j lt len2           if lst1 i  lt lst2 j                    yield lst1 i                  i  1         else                  yield lst2 j                  j  1     if i  len1           while j lt len2                   yield lst2 j                  j  1     elif j  len2           while i lt len1                   yield lst1 i                  i  1 l1  1 3 5 7  l2  2 4 6 8 9  mergelst  val for val in merge l1 l2   print  mergelst

User · Answer

Well  the naive approach  combine 2 lists into large one and sort  will be O N log N   complexity  On the other hand  if you implement the merge manually  i do not know about any ready code in python libs for this  but i m no expert  the complexity will be O N   which is clearly faster  The idea is described wery well in post by Barry Kelly

User · Answer

This is simple merging of two sorted lists  Take a look at the sample code below which merges two sorted lists of integers      usr bin env python    merge py -- Merge two sorted lists - - Python - -    Time-stamp   2009-01-21 14 02 57 ghoseb   l1    1  3  4  7  l2    0  2  5  6  8  9   def merge sorted lists l1  l2          Merge sort two sorted lists      Arguments      -  l1   First sorted list     -  l2   Second sorted list             sorted list             Copy both the args to make sure the original lists are not       modified     l1   l1        l2   l2         while  l1 and l2           if  l1 0   lt   l2 0      Compare both heads             item   l1 pop 0    Pop from the head             sorted list append item          else              item   l2 pop 0              sorted list append item         Add the remaining of the lists     sorted list extend l1 if l1 else l2       return sorted list  if   name         main         print merge sorted lists l1  l2    This should work fine with datetime objects  Hope this helps

User · Answer

If you want to do it in a manner more consistent with learning what goes on in the iteration try this  def merge arrays a  b       l          while len a   gt  0 and len b  gt 0          if a 0   lt  b 0   l append a pop 0               else l append b pop 0        l extend a b      print  l

User · Answer

Python s sort implementation  timsort  is specifically optimized for lists that contain ordered sections   Plus  it s written in C     http   bugs python org file4451 timsort txt http   en wikipedia org wiki Timsort  As people have mentioned  it may call the comparison function more times by some constant factor  but maybe call it more times in a shorter period in many cases        I would never rely on this  however      Daniel Nadasi   I believe the Python developers are committed to keeping timsort  or at least keeping a sort that s O n  in this case      Generalized sorting  i e  leaving apart radix sorts from limited value domains    cannot be done in less than O n log n  on a serial machine      Barry Kelly   Right  sorting in the general case can t be faster than that   But since O   is an upper bound  timsort being O n log n  on arbitrary input doesn t contradict its being O n  given sorted L1    sorted L2

User · Answer

Well  the naive approach  combine 2 lists into large one and sort  will be O N log N   complexity  On the other hand  if you implement the merge manually  i do not know about any ready code in python libs for this  but i m no expert  the complexity will be O N   which is clearly faster  The idea is described wery well in post by Barry Kelly

User · Answer

is there a smarter way to do this in Python   This hasn t been mentioned  so I ll go ahead - there is a merge stdlib function in the heapq module of python 2 6   If all you re looking to do is getting things done  this might be a better idea  Of course  if you want to implement your own  the merge of merge-sort is the way to go    gt  gt  gt  list1    1  5  8  10  50   gt  gt  gt  list2    3  4  29  41  45  49   gt  gt  gt  from heapq import merge  gt  gt  gt  list merge list1  list2    1  3  4  5  8  10  29  41  45  49  50    Here s the documentation

User · Answer

import random      n int input  Enter size of table 1      size of list 1     m int input  Enter size of table 2       size of list 2     tb1  random randrange 1 101 1  for   in range n     filling the list with random     tb2  random randrange 1 101 1  for   in range m     numbers between 1 and 100     tb1 sort     sort the list 1      tb2 sort      sort the list 2     fus       creat an empty list     print tb1     print the list 1     print  ------------------------------------        print tb2     print the list 2     print  ------------------------------------        i 0 j 0     varialbles to cross the list     while i lt n and j lt m           if tb1 i  lt tb2 j                fus append tb1 i                 i  1          else              fus append tb2 j                j  1       if i lt n           fus  tb1 i n       if j lt m           fus  tb2 j m        print fus        this code is used to merge two sorted lists in one sorted list  FUS  without    sorting the  FUS

User · Answer

Recursive implementation is below  Average performance is O n    def merge sorted lists A  B  sorted list   None       if sorted list    None          sorted list           slice index   0     for element in A          if element  lt   B 0               sorted list append element              slice index    1         else              return merge sorted lists B  A slice index    sorted list       return sorted list   B   or generator with improved space complexity   def merge sorted lists as generator A  B       slice index   0     for element in A          if element  lt   B 0               slice index    1             yield element                else              for sorted element in merge sorted lists as generator B  A slice index                     yield sorted element             return              for element in B          yield element

User · Answer

in  O m n  complexity def merge sorted list nums1  list  nums2 list  - gt  list          m   len nums1          n   len nums2                   nums1   nums1 copy           nums2   nums2 copy           nums1 extend  0 for i in range n            while m  gt  0 and n  gt  0              if nums1 m-1   gt   nums2 n-1                   nums1 m n-1    nums1 m-1                  m -  1             else                  nums1 m n-1    nums2 n-1                  n -  1         if n  gt  0              nums1  n    nums2  n          return nums1  l1    1  3  4  7      l2     0  2  5  6  8  9      print merge sorted list l1  l2    output  0  1  2  3  4  5  6  7  8  9

User · Answer

Long story short  unless len l1   l2    1000000 use   L   l1   l2 L sort       Description of the figure and source code can be found here    The figure was generated by the following command     python make-figures py --nsublists 2 --maxn 0x100000 -s merge funcs merge 26 -s merge funcs sort builtin

User · Answer

Well  the naive approach  combine 2 lists into large one and sort  will be O N log N   complexity  On the other hand  if you implement the merge manually  i do not know about any ready code in python libs for this  but i m no expert  the complexity will be O N   which is clearly faster  The idea is described wery well in post by Barry Kelly

User · Answer

Use the  merge  step of merge sort  it runs in O n  time   From wikipedia  pseudo-code    function merge left right      var list result     while length left   gt  0 and length right   gt  0         if first left    first right              append first left  to result             left   rest left          else             append first right  to result             right   rest right      end while     while length left   gt  0          append left to result     while length right   gt  0          append right to result     return result

User · Answer

There is a slight flaw in ghoseb s solution  making it O n  2   rather than O n   The problem is that this is performing   item   l1 pop 0    With linked lists or deques this would be an O 1  operation  so wouldn t affect complexity  but since python lists are implemented as vectors  this copies the rest of the elements of l1 one space left  an O n  operation   Since this is done each pass through the list  it turns an O n  algorithm into an O n  2  one   This can be corrected by using a method that doesn t alter the source lists  but just keeps track of the current position   I ve tried out benchmarking a corrected algorithm vs a simple sorted l1 l2  as suggested by dbr  def merge l1 l2       if not l1   return list l2      if not l2   return list l1         l2 will contain last element      if l1 -1   gt  l2 -1           l1 l2   l2 l1      it   iter l2      y   it next       result           for x in l1          while y  lt  x              result append y              y   it next           result append x      result append y      result extend it      return result   I ve tested these with lists generated with  l1   sorted  random random   for i in range NITEMS    l2   sorted  random random   for i in range NITEMS      For various sizes of list  I get the following timings  repeating 100 times      items   1000   10000 100000 1000000 merge     0 079  0 798 9 763  109 044  sort      0 020  0 217 5 948  106 882   So in fact  it looks like dbr is right  just using sorted   is preferable unless you re expecting very large lists  though it does have worse algorithmic complexity   The break even point being at around a million items in each source list  2 million total    One advantage of the merge approach though is that it is trivial to rewrite as a generator  which will use substantially less memory  no need for an intermediate list     Edit  I ve retried this with a situation closer to the question - using a list of objects containing a field  date  which is a datetime object  The above algorithm was changed to compare against  date instead  and the sort method was changed to   return sorted l1   l2  key operator attrgetter  date      This does change things a bit   The comparison being more expensive means that the number we perform becomes more important  relative to the constant-time speed of the implementation   This means merge makes up lost ground  surpassing the sort   method at 100 000 items instead   Comparing based on an even more complex object  large strings or lists for instance  would likely shift this balance even more     items   1000   10000 100000  1000000 1  merge     0 161  2 034 23 370  253 68 sort      0 111  1 523 25 223  313 20    1   Note  I actually only did 10 repeats for 1 000 000 items and scaled up accordingly as it was pretty slow

User · Answer

Long story short  unless len l1   l2    1000000 use   L   l1   l2 L sort       Description of the figure and source code can be found here    The figure was generated by the following command     python make-figures py --nsublists 2 --maxn 0x100000 -s merge funcs merge 26 -s merge funcs sort builtin

User · Answer

This is simply merging  Treat each list as if it were a stack  and continuously pop the smaller of the two stack heads  adding the item to the result list  until one of the stacks is empty  Then add all remaining items to the resulting list

User · Answer

Long story short  unless len l1   l2    1000000 use   L   l1   l2 L sort       Description of the figure and source code can be found here    The figure was generated by the following command     python make-figures py --nsublists 2 --maxn 0x100000 -s merge funcs merge 26 -s merge funcs sort builtin

User · Answer

There is a slight flaw in ghoseb s solution  making it O n  2   rather than O n   The problem is that this is performing   item   l1 pop 0    With linked lists or deques this would be an O 1  operation  so wouldn t affect complexity  but since python lists are implemented as vectors  this copies the rest of the elements of l1 one space left  an O n  operation   Since this is done each pass through the list  it turns an O n  algorithm into an O n  2  one   This can be corrected by using a method that doesn t alter the source lists  but just keeps track of the current position   I ve tried out benchmarking a corrected algorithm vs a simple sorted l1 l2  as suggested by dbr  def merge l1 l2       if not l1   return list l2      if not l2   return list l1         l2 will contain last element      if l1 -1   gt  l2 -1           l1 l2   l2 l1      it   iter l2      y   it next       result           for x in l1          while y  lt  x              result append y              y   it next           result append x      result append y      result extend it      return result   I ve tested these with lists generated with  l1   sorted  random random   for i in range NITEMS    l2   sorted  random random   for i in range NITEMS      For various sizes of list  I get the following timings  repeating 100 times      items   1000   10000 100000 1000000 merge     0 079  0 798 9 763  109 044  sort      0 020  0 217 5 948  106 882   So in fact  it looks like dbr is right  just using sorted   is preferable unless you re expecting very large lists  though it does have worse algorithmic complexity   The break even point being at around a million items in each source list  2 million total    One advantage of the merge approach though is that it is trivial to rewrite as a generator  which will use substantially less memory  no need for an intermediate list     Edit  I ve retried this with a situation closer to the question - using a list of objects containing a field  date  which is a datetime object  The above algorithm was changed to compare against  date instead  and the sort method was changed to   return sorted l1   l2  key operator attrgetter  date      This does change things a bit   The comparison being more expensive means that the number we perform becomes more important  relative to the constant-time speed of the implementation   This means merge makes up lost ground  surpassing the sort   method at 100 000 items instead   Comparing based on an even more complex object  large strings or lists for instance  would likely shift this balance even more     items   1000   10000 100000  1000000 1  merge     0 161  2 034 23 370  253 68 sort      0 111  1 523 25 223  313 20    1   Note  I actually only did 10 repeats for 1 000 000 items and scaled up accordingly as it was pretty slow

User · Answer

An implementation of the merging step in Merge Sort that iterates through both lists   def merge lists L1  L2               L1  L2  sorted lists of numbers  one of them could be empty       returns a merged and sorted list of L1 and L2                 When one of them is an empty list  returns the other list     if not L1          return L2     elif not L2          return L1      result          i   0     j   0      for k in range len L1    len L2            if L1 i   lt   L2 j               result append L1 i               if i  lt  len L1  - 1                  i    1             else                  result    L2 j      When the last element in L1 is reached                  break               append the rest of L2 to result          else              result append L2 j               if j  lt  len L2  - 1                  j    1             else                  result    L1 i      When the last element in L2 is reached                  break               append the rest of L1 to result       return result  L1    1  3  5  L2    2  4  6  8  merge lists L1  L2                  Should return  1  2  3  4  5  6  8  merge lists     L1                  Should return  1  3  5    I m still learning about algorithms  please let me know if the code could be improved in any aspect  your feedback is appreciated  thanks

User · Answer

def compareDate obj1  obj2       if obj1 getDate    lt  obj2 getDate            return -1     elif obj1 getDate    gt  obj2 getDate            return 1     else          return 0    list   list1   list2 list sort compareDate    Will sort the list in place  Define your own function for comparing two objects  and pass that function into the built in sort function   Do NOT use bubble sort  it has horrible performance

User · Answer

Use the  merge  step of merge sort  it runs in O n  time   From wikipedia  pseudo-code    function merge left right      var list result     while length left   gt  0 and length right   gt  0         if first left    first right              append first left  to result             left   rest left          else             append first right  to result             right   rest right      end while     while length left   gt  0          append left to result     while length right   gt  0          append right to result     return result

User · Answer

This is simply merging  Treat each list as if it were a stack  and continuously pop the smaller of the two stack heads  adding the item to the result list  until one of the stacks is empty  Then add all remaining items to the resulting list

User · Answer

Recursive implementation is below  Average performance is O n    def merge sorted lists A  B  sorted list   None       if sorted list    None          sorted list           slice index   0     for element in A          if element  lt   B 0               sorted list append element              slice index    1         else              return merge sorted lists B  A slice index    sorted list       return sorted list   B   or generator with improved space complexity   def merge sorted lists as generator A  B       slice index   0     for element in A          if element  lt   B 0               slice index    1             yield element                else              for sorted element in merge sorted lists as generator B  A slice index                     yield sorted element             return              for element in B          yield element

User · Answer

from datetime import datetime from itertools import chain from operator import attrgetter  class DT      def   init   self  dt           self dt   dt  list1    DT datetime 2008  12  5  2             DT datetime 2009  1  1  13             DT datetime 2009  1  3  5     list2    DT datetime 2008  12  31  23             DT datetime 2009  1  2  12             DT datetime 2009  1  4  15     list3   sorted chain list1  list2   key attrgetter  dt    for item in list3      print item dt   The output   2008-12-05 02 00 00 2008-12-31 23 00 00 2009-01-01 13 00 00 2009-01-02 12 00 00 2009-01-03 05 00 00 2009-01-04 15 00 00   I bet this is faster than any of the fancy pure-Python merge algorithms  even for large data  Python 2 6 s heapq merge is a whole another story

User · Answer

in  O m n  complexity def merge sorted list nums1  list  nums2 list  - gt  list          m   len nums1          n   len nums2                   nums1   nums1 copy           nums2   nums2 copy           nums1 extend  0 for i in range n            while m  gt  0 and n  gt  0              if nums1 m-1   gt   nums2 n-1                   nums1 m n-1    nums1 m-1                  m -  1             else                  nums1 m n-1    nums2 n-1                  n -  1         if n  gt  0              nums1  n    nums2  n          return nums1  l1    1  3  4  7      l2     0  2  5  6  8  9      print merge sorted list l1  l2    output  0  1  2  3  4  5  6  7  8  9

User · Answer

People seem to be over complicating this   Just combine the two lists  then sort them    gt  gt  gt  l1    1  3  4  7   gt  gt  gt  l2    0  2  5  6  8  9   gt  gt  gt  l1 extend l2   gt  gt  gt  sorted l1   0  1  2  3  4  5  6  7  8  9      or shorter  and without modifying l1     gt  gt  gt  sorted l1   l2   0  1  2  3  4  5  6  7  8  9      easy  Plus  it s using only two built-in functions  so assuming the lists are of a reasonable size  it should be quicker than implementing the sorting merging in a loop  More importantly  the above is much less code  and very readable   If your lists are large  over a few hundred thousand  I would guess   it may be quicker to use an alternative custom sorting method  but there are likely other optimisations to be made first  e g not storing millions of datetime objects   Using the timeit Timer   repeat    which repeats the functions 1000000 times   I loosely benchmarked it against ghoseb s solution  and sorted l1 l2  is substantially quicker   merge sorted lists took     9 7439379692077637  9 8844599723815918  9 552299976348877    sorted l1 l2  took     2 860386848449707  2 7589840888977051  2 7682540416717529

User · Answer

def compareDate obj1  obj2       if obj1 getDate    lt  obj2 getDate            return -1     elif obj1 getDate    gt  obj2 getDate            return 1     else          return 0    list   list1   list2 list sort compareDate    Will sort the list in place  Define your own function for comparing two objects  and pass that function into the built in sort function   Do NOT use bubble sort  it has horrible performance

User · Answer

Hope this helps  Pretty Simple and straight forward   l1    1  3  4  7   l2    0  2  5  6  8  9   l3   l1   l2  l3 sort    print  l3    0  1  2  3  4  5  6  7  8  9

User · Answer

Hope this helps  Pretty Simple and straight forward   l1    1  3  4  7   l2    0  2  5  6  8  9   l3   l1   l2  l3 sort    print  l3    0  1  2  3  4  5  6  7  8  9

User · Answer

def merge sort a b        pa   0     pb   0     result           while pa  lt  len a  and pb  lt  len b           if a pa   lt   b pb               result append a pa               pa    1         else              result append b pb               pb    1      remained   a pa     b pb       result extend remained    return result

User · Answer

is there a smarter way to do this in Python   This hasn t been mentioned  so I ll go ahead - there is a merge stdlib function in the heapq module of python 2 6   If all you re looking to do is getting things done  this might be a better idea  Of course  if you want to implement your own  the merge of merge-sort is the way to go    gt  gt  gt  list1    1  5  8  10  50   gt  gt  gt  list2    3  4  29  41  45  49   gt  gt  gt  from heapq import merge  gt  gt  gt  list merge list1  list2    1  3  4  5  8  10  29  41  45  49  50    Here s the documentation

User · Answer

This is simple merging of two sorted lists  Take a look at the sample code below which merges two sorted lists of integers      usr bin env python    merge py -- Merge two sorted lists - - Python - -    Time-stamp   2009-01-21 14 02 57 ghoseb   l1    1  3  4  7  l2    0  2  5  6  8  9   def merge sorted lists l1  l2          Merge sort two sorted lists      Arguments      -  l1   First sorted list     -  l2   Second sorted list             sorted list             Copy both the args to make sure the original lists are not       modified     l1   l1        l2   l2         while  l1 and l2           if  l1 0   lt   l2 0      Compare both heads             item   l1 pop 0    Pop from the head             sorted list append item          else              item   l2 pop 0              sorted list append item         Add the remaining of the lists     sorted list extend l1 if l1 else l2       return sorted list  if   name         main         print merge sorted lists l1  l2    This should work fine with datetime objects  Hope this helps

User · Answer

Well  the naive approach  combine 2 lists into large one and sort  will be O N log N   complexity  On the other hand  if you implement the merge manually  i do not know about any ready code in python libs for this  but i m no expert  the complexity will be O N   which is clearly faster  The idea is described wery well in post by Barry Kelly

User · Answer

There is a slight flaw in ghoseb s solution  making it O n  2   rather than O n   The problem is that this is performing   item   l1 pop 0    With linked lists or deques this would be an O 1  operation  so wouldn t affect complexity  but since python lists are implemented as vectors  this copies the rest of the elements of l1 one space left  an O n  operation   Since this is done each pass through the list  it turns an O n  algorithm into an O n  2  one   This can be corrected by using a method that doesn t alter the source lists  but just keeps track of the current position   I ve tried out benchmarking a corrected algorithm vs a simple sorted l1 l2  as suggested by dbr  def merge l1 l2       if not l1   return list l2      if not l2   return list l1         l2 will contain last element      if l1 -1   gt  l2 -1           l1 l2   l2 l1      it   iter l2      y   it next       result           for x in l1          while y  lt  x              result append y              y   it next           result append x      result append y      result extend it      return result   I ve tested these with lists generated with  l1   sorted  random random   for i in range NITEMS    l2   sorted  random random   for i in range NITEMS      For various sizes of list  I get the following timings  repeating 100 times      items   1000   10000 100000 1000000 merge     0 079  0 798 9 763  109 044  sort      0 020  0 217 5 948  106 882   So in fact  it looks like dbr is right  just using sorted   is preferable unless you re expecting very large lists  though it does have worse algorithmic complexity   The break even point being at around a million items in each source list  2 million total    One advantage of the merge approach though is that it is trivial to rewrite as a generator  which will use substantially less memory  no need for an intermediate list     Edit  I ve retried this with a situation closer to the question - using a list of objects containing a field  date  which is a datetime object  The above algorithm was changed to compare against  date instead  and the sort method was changed to   return sorted l1   l2  key operator attrgetter  date      This does change things a bit   The comparison being more expensive means that the number we perform becomes more important  relative to the constant-time speed of the implementation   This means merge makes up lost ground  surpassing the sort   method at 100 000 items instead   Comparing based on an even more complex object  large strings or lists for instance  would likely shift this balance even more     items   1000   10000 100000  1000000 1  merge     0 161  2 034 23 370  253 68 sort      0 111  1 523 25 223  313 20    1   Note  I actually only did 10 repeats for 1 000 000 items and scaled up accordingly as it was pretty slow

[python] Combining two sorted lists in Python

Examples related to python

Examples related to list

Examples related to sorting