How to sort in-place using the merge sort algorithm

Question

I know the question is not too specific    All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort  or a merge sort with constant extra space overhead     All I can find  on the net  is pages saying  it is too complex  or  out of scope of this text        The only known ways to merge in-place  without any extra space  are too complex to be reduced to practical program    taken from here    Even if it is too complex  what is the basic concept of how to make the merge sort in-place

User · Answer

This answer has a code example  which implements the algorithm described in the paper Practical In-Place Merging by Bing-Chao Huang and Michael A  Langston  I have to admit that I do not understand the details  but the given complexity of the merge step is O n    From a practical perspective  there is evidence that pure in-place implementations are not performing better in real world scenarios  For example  the C   standard defines std  inplace merge  which is as the name implies an in-place merge operation   Assuming that C   libraries are typically very well optimized  it is interesting to see how it is implemented   1  libstdc    part of the GCC code base   std  inplace merge  The implementation delegates to   inplace merge  which dodges the problem by trying to allocate a temporary buffer   typedef  Temporary buffer lt  BidirectionalIterator   ValueType gt   TmpBuf   TmpBuf   buf   first    len1     len2    if    buf begin      0    std    merge without buffer        first    middle    last    len1    len2    comp   else   std    merge adaptive       first    middle    last    len1    len2    buf begin          DistanceType   buf size       comp     Otherwise  it falls back to an implementation    merge without buffer   which requires no extra memory  but no longer runs in O n  time   2  libc    part of the Clang code base   std  inplace merge  Looks similar  It delegates to a function  which also tries to allocate a buffer  Depending on whether it got enough elements  it will choose the implementation  The constant-memory fallback function is called   buffered inplace merge   Maybe even the fallback is still O n  time  but the point is that they do not use the implementation if temporary memory is available     Note that the C   standard explicitly gives implementations the freedom to choose this approach by lowering the required complexity from O n  to O N log N       Complexity    Exactly N-1 comparisons if enough additional memory is available  If the memory is insufficient  O N log N  comparisons    Of course  this cannot be taken as a proof that constant space in-place merges in O n  time should never be used  On the other hand  if it would be faster  the optimized C   libraries would probably switch to that type of implementation

User · Answer

I just tried in place merge algorithm for merge sort in JAVA by using the insertion sort algorithm  using following steps  1  Two sorted arrays are available  2  Compare the first values of each array  and place the smallest value into the first array  3  Place the larger value into the second array by using insertion sort  traverse from left to right   4  Then again compare the second value of first array and first value of second array  and do the same  But when swapping happens there is some clue on skip comparing the further items  but just swapping required   I have made some optimization here  to keep lesser comparisons in insertion sort  The only drawback i found with this solutions is it needs larger swapping of array elements in the second array    e g   First   Array     3  7  8  9   Second Array   1  2  4  5      Then 7  8  9 makes the second array to swap move left by one  all its elements by one each time to place himself in the last   So the assumption here is swapping items is negligible compare to comparing of two items   https   github com skanagavelu algorithams blob master src sorting MergeSort java   package sorting   import java util Arrays   public class MergeSort       public static void main String   args        int   array     5  6  10  3  9  2  12  1  8  7        mergeSort array  0  array length -1       System out println Arrays toString array         int   array1    4  7  2       System out println Arrays toString array1        mergeSort array1  0  array1 length -1       System out println Arrays toString array1        System out println   n n         int   array2    4  7  9       System out println Arrays toString array2        mergeSort array2  0  array2 length -1       System out println Arrays toString array2        System out println   n n         int   array3    4  7  5       System out println Arrays toString array3        mergeSort array3  0  array3 length -1       System out println Arrays toString array3        System out println   n n         int   array4    7  4  2       System out println Arrays toString array4        mergeSort array4  0  array4 length -1       System out println Arrays toString array4        System out println   n n         int   array5    7  4  9       System out println Arrays toString array5        mergeSort array5  0  array5 length -1       System out println Arrays toString array5        System out println   n n         int   array6    7  4  5       System out println Arrays toString array6        mergeSort array6  0  array6 length -1       System out println Arrays toString array6        System out println   n n           Handling array of size two     int   array7    7  4       System out println Arrays toString array7        mergeSort array7  0  array7 length -1       System out println Arrays toString array7        System out println   n n         int input1      1       int input2      4 2       int input3      6 2 9       int input4      6 -1 10 4 11 14 19 12 18       System out println Arrays toString input1        mergeSort input1  0  input1 length-1       System out println Arrays toString input1        System out println   n n         System out println Arrays toString input2        mergeSort input2  0  input2 length-1       System out println Arrays toString input2        System out println   n n         System out println Arrays toString input3        mergeSort input3  0  input3 length-1       System out println Arrays toString input3        System out println   n n         System out println Arrays toString input4        mergeSort input4  0  input4 length-1       System out println Arrays toString input4        System out println   n n       private static void mergeSort int   array  int p  int r          Both below mid finding is fine      int mid    r - p  2   p      int mid1    r   p  2      if mid    mid1            System out println   Mid is mismatching     mid         mid1     for p   p    r   r              if p  lt  r            mergeSort array  p  mid           mergeSort array  mid 1  r           merge array  p  mid  r           inPlaceMerge array  p  mid  r                      Regular merge private static void merge int   array  int p  int mid  int r        int lengthOfLeftArray   mid - p   1     This is important to add  1      int lengthOfRightArray   r - mid       int   left   new int lengthOfLeftArray       int   right   new int lengthOfRightArray        for int i   p  j   0  i  lt   mid             left j      array i                for int i   mid   1  j   0  i  lt   r             right j      array i                int i   0  j   0      for   i  lt  left length  amp  amp  j  lt  right length              if left i   lt  right j                array p      left i               else               array p      right j                         while j  lt  right length           array p      right j                while i  lt  left length           array p      left i                InPlaceMerge no extra array private static void inPlaceMerge int   array  int p  int mid  int r        int secondArrayStart   mid 1      int prevPlaced   mid 1      int q   mid 1      while p  lt  mid 1  amp  amp  q  lt   r           boolean swapped   false          if array p   gt  array q                 swap array  p  q               swapped   true                       if q    secondArrayStart  amp  amp  array p   gt  array secondArrayStart                 swap array  p  secondArrayStart               swapped   true                      Check swapped value is in right place of second sorted array         if swapped  amp  amp  secondArrayStart 1  lt   r  amp  amp  array secondArrayStart 1   lt  array secondArrayStart                 prevPlaced   placeInOrder array  secondArrayStart  prevPlaced                     p            if q  lt  r          q 1  lt   r                q                       private static int placeInOrder int   array  int secondArrayStart  int prevPlaced        int i   secondArrayStart      for   i  lt  array length  i                Simply swap till the prevPlaced position         if secondArrayStart  lt  prevPlaced                swap array  secondArrayStart  secondArrayStart 1               secondArrayStart                continue                    if array i   lt  array secondArrayStart                 swap array  i  secondArrayStart               secondArrayStart              else if i    secondArrayStart  amp  amp  array i   gt  array secondArrayStart                break                      return secondArrayStart     private static void swap int   array  int m  int n       int temp   array m       array m    array n       array n    temp

User · Answer

Knuth left this as an exercise  Vol 3  5 2 5   There do exist in-place merge sorts  They must be implemented carefully  First  naive in-place merge such as described here isn t the right solution  It downgrades the performance to O N2   The idea is to sort part of the array while using the rest as working area for merging  For example like the following merge function   void wmerge Key  xs  int i  int m  int j  int n  int w        while  i  lt  m  amp  amp  j  lt  n          swap xs  w    xs i   lt  xs j    i     j         while  i  lt  m          swap xs  w    i         while  j  lt  n          swap xs  w    j          It takes the array xs  the two sorted sub-arrays are represented as ranges  i  m  and  j  n  respectively  The working area starts from w  Compare with the standard merge algorithm given in most textbooks  this one exchanges the contents between the sorted sub-array and the working area  As the result  the previous working area contains the merged sorted elements  while the previous elements stored in the working area are moved to the two sub-arrays  However  there are two constraints that must be satisfied   The work area should be within the bounds of the array  In other words  it should be big enough to hold elements exchanged in without causing any out-of-bound error  The work area can be overlapped with either of the two sorted arrays  however  it must ensure that none of the unmerged elements are overwritten   With this merging algorithm defined  it s easy to imagine a solution  which can sort half of the array  The next question is  how to deal with the rest of the unsorted part stored in work area as shown below      unsorted 1 2 array           sorted 1 2 array      One intuitive idea is to recursive sort another half of the working area  thus there are only 1 4 elements haven t been sorted yet      unsorted 1 4 array       sorted 1 4 array B   sorted 1 2 array A      The key point at this stage is that we must merge the sorted 1 4 elements B with the sorted 1 2 elements A sooner or later  Is the working area left  which only holds 1 4 elements  big enough to merge A and B  Unfortunately  it isn t  However  the second constraint mentioned above gives us a hint  that we can exploit it by arranging the working area to overlap with either sub-array if we can ensure the merging sequence that the unmerged elements won t be overwritten  Actually  instead of sorting the second half of the working area  we can sort the first half  and put the working area between the two sorted arrays like this      sorted 1 4 array B   unsorted work area       sorted 1 2 array A      This setup effectively arranges the work area overlap with the sub-array A  This idea is proposed in  Jyrki Katajainen  Tomi Pasanen  Jukka Teuhola    Practical in-place mergesort    Nordic Journal of Computing  1996   So the only thing left is to repeat the above step  which reduces the working area from 1 2  1 4  1 8      When the working area becomes small enough  for example  only two elements left   we can switch to a trivial insertion sort to end this algorithm  Here is the implementation in ANSI C based on this paper  void imsort Key  xs  int l  int u    void swap Key  xs  int i  int j        Key tmp   xs i   xs i    xs j   xs j    tmp            sort xs l  u   and put result to working area w      constraint  len w     u - l     void wsort Key  xs  int l  int u  int w        int m      if  u - l  gt  1            m   l    u - l    2          imsort xs  l  m           imsort xs  m  u           wmerge xs  l  m  m  u  w             else         while  l  lt  u              swap xs  l    w        void imsort Key  xs  int l  int u        int m  n  w      if  u - l  gt  1            m   l    u - l    2          w   l   u - m          wsort xs  l  m  w      the last half contains sorted elements            while  w - l  gt  2                n   w              w   l    n - l   1    2              wsort xs  w  n  l       the first half of the previous working area contains sorted elements                wmerge xs  l  l   n - w  n  u  w                     for  n   w  n  gt  l  --n    switch to insertion sort               for  m   n  m  lt  u  amp  amp  xs m   lt  xs m-1     m                  swap xs  m  m - 1            Where wmerge is defined previously  The full source code can be found here and the detailed explanation can be found here By the way  this version isn t the fastest merge sort because it needs more swap operations  According to my test  it s faster than the standard version  which allocates extra spaces in every recursion  But it s slower than the optimized version  which doubles the original array in advance and uses it for further merging

User · Answer

It really isn t easy or efficient  and I suggest you don t do it unless you really have to  and you probably don t have to unless this is homework since the applications of inplace merging are mostly theoretical   Can t you use quicksort instead  Quicksort will be faster anyway with a few simpler optimizations and its extra memory is O log N    Anyway  if you must do it then you must  Here s what I found  one and two  I m not familiar with the inplace merge sort  but it seems like the basic idea is to use rotations to facilitate merging two arrays without using extra memory   Note that this is slower even than the classic merge sort that s not inplace

User · Answer

An example of bufferless mergesort in C    define SWAP type  a  b        do   type t  a   a   b   b  t    while  0   static void reverse  int  a  int  b        for   --b  a  lt  b  a    b--          SWAP int   a   b     static int  rotate  int  a  int  b  int  c     swap the sequence  a b  with  b c            if  a    b  amp  amp  b    c                reverse  a  b          reverse  b  c          reverse  a  c              return a    c - b      static int  lower bound  int  a  int  b  const int key     find first element not less than  p key in sorted sequence or end of    sequence   p b  if not found           int i      for   i   b-a  i    0  i    2                 int  mid   a   i 2         if   mid  lt  key            a   mid   1  i--             return a    static int  upper bound  int  a  int  b  const int key     find first element greater than  p key in sorted sequence or end of    sequence   p b  if not found           int i      for   i   b-a  i    0  i    2                 int  mid   a   i 2         if   mid  lt   key            a   mid   1  i--             return a     static void ip merge  int  a  int  b  int  c     inplace merge           int n1   b - a      int n2   c - b       if  n1    0    n2    0         return      if  n1    1  amp  amp  n2    1                if   b  lt   a            SWAP int   a   b              else               int  p    q          if  n1  lt   n2            p   upper bound  a  b    q   b n2 2           else           q   lower bound  b  c    p   a n1 2           b   rotate  p  b  q           ip merge  a  p  b          ip merge  b  q  c             void mergesort int  v  int n        if  n  gt  1                int h   n 2         mergesort v  h   mergesort v h  n-h          ip merge  v  v h  v n              An example of adaptive mergesort  optimized    Adds support code and modifications to accelerate the merge when an auxiliary buffer of any size is available  still works without additional memory   Uses forward and backward merging  ring rotation  small sequence merging and sorting  and iterative mergesort    include  lt stdlib h gt   include  lt string h gt   static int  copy  const int  a  const int  b  int  out        int count   b - a      if  a    out         memcpy out  a  count sizeof int        return out   count    static int  copy backward  const int  a  const int  b  int  out        int count   b - a      if  b    out         memmove out - count  a  count sizeof int        return out - count     static int  merge  const int  a1  const int  b1  const int  a2    const int  b2  int  out        while   a1    b1  amp  amp  a2    b2           out       a1  lt    a2     a1      a2        return copy  a2  b2  copy  a1  b1  out      static int  merge backward  const int  a1  const int  b1    const int  a2  const int  b2  int  out        while   a1    b1  amp  amp  a2    b2           --out      b1-1   gt    b2-1      --b1    --b2      return copy backward  a1  b1  copy backward  a2  b2  out       static unsigned int gcd  unsigned int m  unsigned int n        while   n    0                 unsigned int t   m   n         m   n         n   t             return m    static void rotate inner  const int length  const int stride    int  first  int  last        int  p    next   first  x    first      while   1                 p   next         if   next    stride   gt   last            next -  length         if  next    first            break          p    next              p   x    static int  rotate  int  a  int  b  int  c     swap the sequence  a b  with  b c            if  a    b  amp  amp  b    c                int n1   c - a         int n2   b - a          int  i   a         int  j   a   gcd  n1  n2           for     i    j  i               rotate inner  n1  n2  i  c              return a    c - b      static void ip merge small  int  a  int  b  int  c     inplace merge      note faster for small sequences           while   a    b  amp  amp  b    c          if   a  lt    b            a           else                     int  p   b 1            while   p    c  amp  amp   p  lt   a                p              rotate  a  b  p             b   p              static void ip merge  int  a  int  b  int  c  int  t  const int ts     inplace merge      note works with or without additional memory           int n1   b - a      int n2   c - b       if  n1  lt   n2  amp  amp  n1  lt   ts                merge  t  copy  a  b  t   b  c  a              else if  n2  lt   ts                merge backward  a  b  t  copy  b  c  t   c                 merge without buffer         else if  n1   n2  lt  48                ip merge small  a  b  c              else               int  p    q          if  n1  lt   n2            p   upper bound  a  b    q   b n2 2           else           q   lower bound  b  c    p   a n1 2           b   rotate  p  b  q           ip merge  a  p  b  t  ts          ip merge  b  q  c  t  ts            static void ip merge chunk  const int cs  int  a  int  b  int  t    const int ts        int  p   a   cs 2      for     p  lt   b  a   p  p    cs 2          ip merge  a  a cs  p  t  ts       if  a cs  lt  b         ip merge  a  a cs  b  t  ts      static void smallsort  int  a  int  b     insertion sort      note any stable sort with low setup cost will do           int  p    q      for   p   a 1  p  lt  b  p                   int x    p         for   q   p  a  lt  q  amp  amp  x  lt    q-1   q--              q     q-1           q   x           static void smallsort chunk  const int cs  int  a  int  b        int  p   a   cs      for     p  lt   b  a   p  p    cs          smallsort  a  p       smallsort  a  b      static void mergesort lower  int  v  int n  int  t  const int ts        int cs   16      smallsort chunk  cs  v  v n       for     cs  lt  n  cs    2          ip merge chunk  cs  v  v n  t  ts      static void  get buffer  int size  int  final        void  p   NULL      while   size    0  amp  amp   p   malloc size      NULL          size    2       final   size      return p    void mergesort int  v  int n            note buffer size may be in the range  0  n 1  2          int request    n 1  2   sizeof int       int actual      int  t    int   get buffer  request   amp actual            note allocation failure okay         int tsize   actual   sizeof int       mergesort lower  v  n  t  tsize       free t

User · Answer

The critical step is getting the merge itself to be in-place  It s not as difficult as those sources make out  but you lose something when you try   Looking at one step of the merge          list-sorted    x   list-A    y   list-B       We know that the sorted sequence is less than everything else  that x is less than everything else in A  and that y is less than everything else in B  In the case where x is less than or equal to y  you just move your pointer to the start of A on one  In the case where y is less than x  you ve got to shuffle y past the whole of A to sorted  That last step is what makes this expensive  except in degenerate cases    It s generally cheaper  especially when the arrays only actually contain single words per element  e g   a pointer to a string or structure  to trade off some space for time and have a separate temporary array that you sort back and forth between

User · Answer

This is my C version   void mergesort int  a  int len      int temp  listsize  xsize     for  listsize   1  listsize  lt   len  listsize  2        for  int i   0  j   listsize   j listsize   lt   len  i     listsize 2   j     listsize 2           merge  amp  a i   listsize  listsize                listsize    2     xsize   len   listsize    if  xsize  gt  1      mergesort  amp  a len-xsize   xsize      merge a  listsize  xsize      void merge int  a  int sizei  int sizej      int temp    int ii   0    int ji   sizei    int flength   sizei sizej     for  int f   0  f  lt   flength-1   f          if  sizei    0    sizej    0        break       if  a ii   lt  a ji           ii          sizei--            else         temp   a ji          for  int z    ji-1   z  gt   ii  z--          a z 1    a z           ii           a f    temp         ji          sizej--

User · Answer

Just for reference  here is a nice implementation of a stable in-place merge sort  Complicated  but not too bad   I ended up implementing both a stable in-place merge sort and a stable in-place quicksort in Java  Please note the complexity is O n  log n  2

User · Answer

Including its  big result   this paper describes a couple of variants of in-place merge sort  PDF    http   citeseerx ist psu edu viewdoc download doi 10 1 1 22 5514 amp rep rep1 amp type pdf  In-place sorting with fewer moves  Jyrki Katajainen  Tomi A  Pasanen      It is shown that an array of n   elements can be sorted using O 1    extra space  O n log n   log log n    element moves  and n log2n   O n log   log n  comparisons  This is the first   in-place sorting algorithm requiring   o n log n  moves in the worst case   while guaranteeing O n log n    comparisons  but due to the constant   factors involved the algorithm is   predominantly of theoretical interest    I think this is relevant too  I have a printout of it lying around  passed on to me by a colleague  but I haven t read it  It seems to cover basic theory  but I m not familiar enough with the topic to judge how comprehensively   http   comjnl oxfordjournals org cgi content abstract 38 8 681  Optimal Stable Merging  Antonios Symvonis     This paper shows how to stably merge   two sequences A and B  of sizes m and   n  m   n  respectively  with O m n    assignments  O mlog n m 1     comparisons and using only a constant   amount of additional space  This   result matches all known lower bounds

User · Answer

There is a relatively simple implementation of in-place merge sort using Kronrod s original technique but with simpler implementation  A pictorial example that illustrates this technique can be found here  http   www logiccoder com TheSortProblem BestMergeInfo htm    There are also links to more detailed theoretical analysis by the same author associated with this link

[arrays] How to sort in-place using the merge sort algorithm?

1) libstdc++ (part of the GCC code base): std::inplace_merge

2) libc++ (part of the Clang code base): std::inplace_merge

Examples related to arrays

Examples related to algorithm

Examples related to sorting

Examples related to mergesort

Examples related to in-place