Mergesort with Python

Question

I couldn t find any working Python 3 3 mergesort algorithm codes  so I made one myself  Is there any way to speed it up  It sorts 20 000 numbers in about 0 3-0 5 seconds  def msort x       result          if len x   lt  2          return x     mid   int len x  2      y   msort x  mid       z   msort x mid        while  len y   gt  0  or  len z   gt  0           if len y   gt  0 and len z   gt  0              if y 0   gt  z 0                   result append z 0                   z pop 0              else                  result append y 0                   y pop 0          elif len z   gt  0              for i in z                  result append i                  z pop 0          else              for i in y                  result append i                  y pop 0      return result

User · Answer

If you change your code like that it ll be working   def merge sort arr       if len arr   lt  2          return arr        middle of arr   len arr    2     left   arr 0 middle of arr      right   arr middle of arr       left side   merge sort left      right side   merge sort right      return merge left side  right side   def merge left side  right side       result          while len left side   gt  0 or len right side   gt  0          if len left side   gt  0 and len right side   gt  0              if left side 0   lt   right side 0                   result append left side pop 0               else                  result append right side pop 0           elif len left side   gt  0              result append left side pop 0           elif len right side   gt  0              result append right side pop 0       return result  arr    6  5  4  3  2  1    print merge sort arr     1  2  3  4  5  6

User · Answer

Here is the CLRS Implementation   def merge arr  p  q  r       n1   q - p   1     n2   r - q     right  left              for i in range n1           left append arr p   i       for j in range n2           right append arr q   j   1       left append float  inf        right append float  inf        i   j   0     for k in range p  r   1           if left i   lt   right j               arr k    left i              i    1         else              arr k    right j              j    1   def merge sort arr  p  r       if p  lt  r          q    p   r     2         merge sort arr  p  q          merge sort arr  q   1  r          merge arr  p  q  r    if   name         main         test    5  2  4  7  1  3  2  6      merge sort test  0  len test  - 1      print test   Result    1  2  2  3  4  5  6  7

User · Answer

def merge a low mid high           l a low mid 1          r a mid 1 high 1           print l r          k 0 i 0 j 0          c  0 for i in range low high 1           while i lt len l  and j lt len r                if l i  lt  r j                     c k   l i                   k  1                  i  1             else                  c k   r j                   j  1                 k  1         while i lt len l                c k   l i               k  1             i  1          while j lt len r                c k   r j               k  1             j  1          print c            a low high 1  c        def mergesort a low high           if high gt low               mid  low high   2               mergesort a low mid              mergesort a mid 1 high              merge a low mid high       a  12 8 3 2 9 0      mergesort a 0 len a -1      print a

User · Answer

A longer one that counts inversions and adheres to the sorted interface  It s trivial to modify this to make it a method of an object that sorts in place   import operator  class MergeSorted       def   init   self           self inversions   0      def   call   self  l  key None  reverse False            self inversions   0          if key is None              self key   lambda x  x         else              self key   key          if reverse              self compare   operator gt         else              self compare   operator lt          dest   list l          working    0    len l          self inversions   self  merge sort dest  working  0  len dest           return dest      def  merge sort self  dest  working  low  high           if low  lt  high - 1              mid    low   high     2             x   self  merge sort dest  working  low  mid              y   self  merge sort dest  working  mid  high              z   self  merge dest  working  low  mid  high              return  x   y   z          else              return 0      def  merge self  dest  working  low  mid  high           i   0         j   0         inversions   0          while  low   i  lt  mid  and  mid   j  lt  high               if self compare self key dest low   i    self key dest mid   j                     working low   i   j    dest low   i                  i    1             else                  working low   i   j    dest mid   j                  inversions     mid -  low   i                   j    1          while low   i  lt  mid              working low   i   j    dest low   i              i    1          while mid   j  lt  high              working low   i   j    dest mid   j              j    1          for k in range low  high               dest k    working k           return inversions   msorted   MergeSorted     Uses   gt  gt  gt  l    5  2  3  1  4   gt  gt  gt  s   msorted l   gt  gt  gt  s  1  2  3  4  5   gt  gt  gt  msorted inversions 6   gt  gt  gt  l     e    b    c    a    d    gt  gt  gt  d     a   10            b   4            c   2            d   5            e   9   gt  gt  gt  key   lambda x  d x   gt  gt  gt  s   msorted l  key key   gt  gt  gt  s   c    b    d    e    a    gt  gt  gt  msorted inversions 5   gt  gt  gt  l    5  2  3  1  4   gt  gt  gt  s   msorted l  reverse True   gt  gt  gt  s  5  4  3  2  1   gt  gt  gt  msorted inversions 4   gt  gt  gt  l     e    b    c    a    d    gt  gt  gt  d     a   10            b   4            c   2            d   5            e   9   gt  gt  gt  key   lambda x  d x   gt  gt  gt  s   msorted l  key key  reverse True   gt  gt  gt  s   a    e    d    b    c    gt  gt  gt  msorted inversions 5

User · Answer

def merge x       if len x     1          return x     else          mid   int len x    2          l   merge x  mid           r   merge x mid        i   j   0     result          while i  lt  len l  and j  lt  len r           if l i   lt  r j               result append l i               i    1         else              result append r j               j    1     result    l i       result    r j       return result

User · Answer

Glad there are tons of answers  I hope you find this one to be clear  concise  and fast   Thank you  import math  def merge array ar1  ar2       c  i  j      0  0      while i  lt  len ar1  and j  lt  len ar2           if  ar1 i   lt  ar2 j               c append ar1 i               i  1         else              c append ar2 j               j  1          return c   ar1 i     ar2 j    def mergesort array       n   len array      if n    1          return array     half n    math floor n 2        ar1  ar2   mergesort array  half n    mergesort array half n        return merge array ar1  ar2

User · Answer

Take my implementation  def merge sort sequence               Sequence of numbers is taken as input  and is split into two halves  following which they are recursively sorted              if len sequence   lt  2          return sequence      mid   len sequence     2       note  7  2   3  whereas 7 2   3 5      left sequence   merge sort sequence  mid       right sequence   merge sort sequence mid         return merge left sequence  right sequence   def merge left  right               Traverse both sorted sub-arrays  left and right   and populate the result array             result          i   j   0     while i  lt  len left  and j  lt  len right           if left i   lt  right j               result append left i               i    1         else              result append right j               j    1     result    left i       result    right j        return result    Print the sorted list  print merge sort  5  2  6  8  5  8  1

User · Answer

This is very similar to the  MIT  solution and a couple others above  but answers the question in a little more  Pythonic  manner by passing references to the left and right partitions instead of positional indexes  and by using a range in the for loop with slice notation to fill in the sorted array   def merge sort array       n   len array      if n  gt  1          mid   n  2         left   array 0 mid          right   array mid n          print mid  left  right  array          merge sort left          merge sort right          merge left  right  array   def merge left  right  array       array length   len array      right length   len right      left length   len left      left index   right index   0     for array index in range 0  array length           if right index    right length              array array index array length    left left index left length              break         elif left index    left length              array array index array length    right right index right length              break         elif left left index   lt   right right index                   array array index    left left index                  left index    1         else              array array index    right right index              right index    1  array    99 2 3 3 12 4 5  arr len   len array  merge sort array  print array  assert len array     arr len   This solution finds the left and right partitions using Python s handy    operator  and then passes the left  right  and array references to the merge function  which in turn rebuilds the original array in place   The trick is in the cleanup  when you have reached the end of either the left or the right partition  the original array is filled in with whatever is left over in the other partition

User · Answer

As already said  l pop 0  is a O len l   operation and must be avoided  the above msort function is O n  2   If efficiency matter  indexing is better but have cost too  The for x in l is faster but not easy to implement for mergesort   iter can be used instead here  Finally  checking i  lt  len l  is made twice because tested again when accessing the element   the exception mechanism  try except  is better  and give a last improvement of 30     def msort l       if len l  gt 1          t len l   2         it1 iter msort l  t    x1 next it1          it2 iter msort l t     x2 next it2          l            try              while True                  if x1 lt  x2  l append x1  x1 next it1                  else       l append x2  x2 next it2          except              if x1 lt  x2  l append x2  l extend it2              else       l append x1  l extend it1      return l

User · Answer

Try this recursive version  def mergeList l1 l2       l3        Tlen len l1  len l2      inf  float  inf       for i in range Tlen           print    l1    l1 0    l2    l2 0          if l1 0  lt  l2 0               l3 append l1 0               del l1 0              l1 append inf          else              l3 append l2 0               del l2 0              l2 append inf      return l3  def main        l1  2 10 7 6 8      print mergeSort breaklist l1    def breaklist rawlist       newlist        for atom in rawlist          print atom         list atom  atom          newlist append list atom      return newlist  def mergeSort inputList       listlen len inputList      if listlen   1          return inputList     else          newlist            if listlen   2  0              for i in range listlen 2                   newlist append mergeList inputList 2 i  inputList 2 i 1            else              for i in range  listlen 1  2                   if 2 i 1 lt listlen                      newlist append mergeList inputList 2 i  inputList 2 i 1                    else                      newlist append inputList 2 i           return  mergeSort newlist   if   name         main         main

User · Answer

Loops like this can probably be speeded up   for i in z      result append i      z pop 0    Instead  simply do this   result extend z    Note that there is no need to clean the contents of z because you won t use it anyway

User · Answer

You can initialise the whole result list in the top level call to mergesort   result    0  len x      replace 0 with a suitable default element if necessary                           or just copy x  result   x       Then for the recursive calls you can use a helper function to which you pass not sublists  but indices into x  And the bottom level calls read their values from x and write into result directly   That way you can avoid all that poping and appending which should improve performance

User · Answer

After implementing different versions of solution   I finally made a trade-off to achieve these goals based on CLRS version   Goal   not using list pop   to iterate values not creating a new list for saving result  modifying the original one instead not using float  inf   as sentinel values   def mergesort A  p  r       if p  lt  r           q    p r   2         mergesort A  p  q          mergesort A  q 1  r          merge A  p  q  r    def merge A  p  q  r       L   A p q 1      R   A q 1 r 1      i   0     j   0     k   p     while i  lt  len L  and j  lt  len R           if L i   lt  R j                A k    L i              i    1         else              A k    R j              j    1         k    1     if i  lt  len L           A k r 1    L i     if   name         main         items    6  2  9  1  7  3  4  5  8      mergesort items  0  len items -1      print items     assert items     1  2  3  4  5  6  7  8  9    Reference   1  Book  CLRS   2  https   github com gzc CLRS blob master C02-Getting-Started exercise code merge-sort py

User · Answer

The first improvement would be to simplify the three cases in the main loop  Rather than iterating while some of the sequence has elements  iterate while both sequences have elements  When leaving the loop  one of them will be empty  we don t know which  but we don t care  We append them at the end of the result   def msort2 x       if len x   lt  2          return x     result                 moved      mid   int len x    2      y   msort2 x  mid       z   msort2 x mid        while  len y   gt  0  and  len z   gt  0           if y 0   gt  z 0               result append z 0               z pop 0          else              result append y 0               y pop 0      result    y     result    z     return result   The second optimization is to avoid popping the elements  Rather  have two indices   def msort3 x       if len x   lt  2          return x     result          mid   int len x    2      y   msort3 x  mid       z   msort3 x mid        i   0     j   0     while i  lt  len y  and j  lt  len z           if y i   gt  z j               result append z j               j    1         else              result append y i               i    1     result    y i       result    z j       return result   A final improvement consists in using a non recursive algorithm to sort short sequences  In this case I use the built-in sorted function and use it when the size of the input is less than 20   def msort4 x       if len x   lt  20          return sorted x      result          mid   int len x    2      y   msort4 x  mid       z   msort4 x mid        i   0     j   0     while i  lt  len y  and j  lt  len z           if y i   gt  z j               result append z j               j    1         else              result append y i               i    1     result    y i       result    z j       return result   My measurements to sort a random list of 100000 integers are 2 46 seconds for the original version  2 33 for msort2  0 60 for msort3 and 0 40 for msort4  For reference  sorting all the list with sorted takes 0 03 seconds

User · Answer

Many have answered this question correctly  this is just another solution  although my solution is very similar to Max Montana  but I have few differences for implementation   let s review the general idea here before we get to the code    Divide the list into two roughly equal halves   Sort the left half  Sort the right half   Merge the two sorted halves into one sorted list    here is the code  tested with python 3 7    def merge left right       result         i j 0 0     while i lt len left  and j lt len right           if left i   lt  right j               result append left i               i  1         else              result append right j               j  1     result extend left i      since we want to add each element and not the object list     result extend right j        return result  def merge sort data       if len data   1          return data     middle len data   2     left data merge sort data  middle       right data merge sort data middle        return merge left data right data    data  100 5 200 3 100 4 8 9   print merge sort data

User · Answer

A little late the the party  but I figured I d throw my hat in the ring as my solution seems to run faster than OP s  on my machine  anyway       Python 3  def merge sort arr       if len arr   lt  2          return arr     half   len arr     2     left   merge sort arr  half       right   merge sort arr half        out          li   ri   0    index of next element from left  right halves     while True          if li  gt   len left      left half is exhausted             out extend right ri                break         if ri  gt   len right     right half is exhausted             out extend left li                break         if left li   lt  right ri               out append left li               li    1         else              out append right ri               ri    1     return out   This doesn t have any slow pop  s  and once one of the half-arrays is exhausted  it immediately extends the other one onto the output array rather than starting a new loop    I know it s machine dependent  but for 100 000 random elements  above merge sort   vs  Python built-in sorted      merge sort  1 03605 seconds Python sort  0 045 seconds Ratio merge   Python sort  23 0229

User · Answer

from run time import run time from random arr import make arr  def merge arr1  list  arr2  list       temp          x  y   0  0     while len arr1  and len arr2           if arr1 0   lt  arr2 0               temp append arr1 0               x    1             arr1   arr1 x           elif arr1 0   gt  arr2 0               temp append arr2 0               y    1             arr2   arr2 y           else              temp append arr1 0               temp append arr2 0               x    1             y    1             arr1   arr1 x               arr2   arr2 y        if len arr1   gt  0          temp    arr1     if len arr2   gt  0          temp    arr2     return temp   run time def merge sort arr  list       total   len arr      step   2     while True          for i in range 0  total  step               arr i i   step    merge arr i i   step  2   arr i   step  2 i   step           step    2         if step  gt  2   total              return arr  arr   make arr 20000  merge sort arr    run time is 0 10300588607788086

User · Answer

def merge sort x        if len x   lt  2 return x      result mid      int len x  2       y   merge sort x  mid       z   merge sort x mid         while  len y   gt  0  and  len z   gt  0               if y 0   gt  z 0  result append z pop 0                  else result append y pop 0        result extend y z      return result

User · Answer

here is another solution  class MergeSort object       def  merge self left  right           nl   len left          nr   len right          result    0   nl nr          i 0         j 0         for k in range len result                if nl gt i and nr gt j                  if left i   lt   right j                       result k  left i                      i  1                 else                      result k  right j                      j  1             elif nl  i                  result k    right j                  j  1             else   nr gt j                  result k    left i                  i  1         return result      def sort self arr           n   len arr          if n lt  1              return arr          left   self sort arr  n 2           right   self sort arr n 2             return self  merge left  right  def main        import random     a  range 100000      random shuffle a      mr clss   MergeSort       result   mr clss sort a       print result  if   name         main         main     and here is run time for list with 100000 elements   real    0m1 073s user    0m1 053s sys         0m0 017s

User · Answer

here is my answer using two function one for merge and another for divide and    conquer  l int input  enter range len          c list range l 0 -1   print  list before sorting is  c  def mergesort1 c l r           i j k 0 0 0     while  i lt len l   amp  j lt len r            if l i  lt r j               c k  l i              i   1                     else              c k  r j              j   1         k   1     while i lt len l           c k  l i          i  1         k  1     while j lt len r           c k  r j          j  1         k  1     return c    def mergesort c       if len c  lt 2          return c     else          l c 0  len c   2           r c len c   2 len c           mergesort l          mergesort r      return    mergesort1 c l r

User · Answer

Code from MIT course   with generic cooperator    import operator   def merge left  right  compare       result          i  j   0  0     while i  lt  len left  and j  lt  len right           if compare left i   right j                result append left i               i    1         else              result append right j               j    1     while i  lt  len left           result append left i           i    1     while j  lt  len right           result append right j           j    1     return result   def mergeSort L  compare operator lt       if len L   lt  2          return L        else          middle   int len L    2          left   mergeSort L  middle   compare          right   mergeSort L middle    compare          return merge left  right  compare

User · Answer

The following code pops at the end  efficient enough  and sorts inplace despite returning as well   def mergesort lis       if len lis   gt  1          left  right   map lambda l  list reversed mergesort l      lis   2   lis 1  2            lis clear           while left and right              lis append left pop   if left -1   lt  right -1  else right pop            lis extend left   -1           lis extend right   -1       return lis

User · Answer

def merge arr  p  q  r       left   arr p q   1      right   arr q   1 r   1      left append float  inf        right append float  inf        i   j   0     for k in range p  r   1           if left i   lt   right j               arr k    left i              i    1         else              arr k    right j              j    1   def init func function       def wrapper  args           a              if len args     1              a   args 0                   function a  0  len a  - 1          else              function  args          return a      return wrapper    init func def merge sort arr  p  r       if p  lt  r          q    p   r     2         merge sort arr  p  q          merge sort arr  q   1  r          merge arr  p  q  r  if   name         main         test    5  4  3  2  1      print merge sort test     Result would be   1  2  3  4  5

User · Answer

def mergeSort alist       print  Splitting   alist      if len alist  gt 1          mid   len alist   2         lefthalf   alist  mid          righthalf   alist mid            mergeSort lefthalf          mergeSort righthalf           i 0         j 0         k 0         while i  lt  len lefthalf  and j  lt  len righthalf               if lefthalf i   lt  righthalf j                   alist k  lefthalf i                  i i 1             else                  alist k  righthalf j                  j j 1             k k 1          while i  lt  len lefthalf               alist k  lefthalf i              i i 1             k k 1          while j  lt  len righthalf               alist k  righthalf j              j j 1             k k 1     print  Merging   alist   alist    54 26 93 17 77 31 44 55 20  mergeSort alist  print alist

User · Answer

def merge l1  l2  out          if l1      return out l2     if l2      return out l1     if l1 0  lt l2 0   return merge l1 1    l2  out l1 0 1       return merge l1  l2 1    out l2 0 1   def merge sort l   return  lambda h  l if h lt 1 else merge merge sort l  h    merge sort l h      len l  2  print merge sort  1 4 6 3 2 5 78 4 2 1 4 6 8

[python] Mergesort with Python

Examples related to python

Examples related to python-3.x

Examples related to algorithm

Examples related to sorting

Examples related to mergesort