How to merge two sorted arrays into a sorted array

Question

This was asked of me in an interview and this is the solution I provided   public static int   merge int   a  int   b         int   answer   new int a length   b length       int i   0  j   0  k   0      while  i  lt  a length  amp  amp  j  lt  b length                if  a i   lt  b j                         answer k    a i               i                      else                       answer k    b j               j                      k               while  i  lt  a length                answer k    a i           i            k               while  j  lt  b length                answer k    b j           j            k               return answer      Is there a more efficient way to do this    Edit  Corrected length methods

User · Answer

You can use ternary operators for making the code a bit more compact  public static int   mergeArrays int   a1  int   a2        int   res   new int a1 length   a2 length       int i   0  j   0       while  i  lt  a1 length  amp  amp  j  lt  a2 length            res i   j    a1 i   lt  a2 j    a1 i      a2 j                while  i  lt  a1 length            res i   j    a1 i                while  j  lt  a2 length            res i   j    a2 j                return res

User · Answer

public static int   mergeSorted int   left  int   right        System out println  merging     Arrays toString left      and     Arrays toString right        int   merged   new int left length   right length       int nextIndexLeft   0      int nextIndexRight   0      for  int i   0  i  lt  merged length  i              if  nextIndexLeft  gt   left length                System arraycopy right  nextIndexRight  merged  i  right length - nextIndexRight               break                    if  nextIndexRight  gt   right length                System arraycopy left  nextIndexLeft  merged  i  left length - nextIndexLeft               break                    if  left nextIndexLeft   lt   right nextIndexRight                 merged i    left nextIndexLeft               nextIndexLeft                continue                    if  left nextIndexLeft   gt  right nextIndexRight                 merged i    right nextIndexRight               nextIndexRight                continue                      System out println  merged       Arrays toString merged        return merged      Just a small different from the original solution

User · Answer

GallopSearch Merge  O log n  log i   rather than O n   I went ahead and implemented greybeard suggestion in the comments  Mostly because I needed a highly efficient mission critical version of this code    The code uses a gallopSearch which is O log i   where i is the distance from the current index the relevant index exists  The code uses a binarySearch for after the gallop search has identified the proper range  Since gallop limited this to a smaller range the resulting binarySearch is also O log i   The gallop and merge are performed backwards  This doesn t seem mission critical but it allows in place merging of arrays  If one of your arrays has enough room to store the results values  you can simply use it as the merging array and the results array  You must specify the valid range within the array in such a case  It does not require memory allocation in that case  big savings in critical operations   It simply makes sure it doesn t and cannot overwrite any unprocessed values  which can only be done backwards   In fact  you use the same array for both of the inputs and the results  It will suffer no ill effects  I consistently used Integer compare   so this could be switched out for other purposes  There s some chance I might have goofed a little and not utilized information I have previously proven  Such as binary searching into a range of two values  for which one value was already checked  There might also be a better way to state the main loop  the flipping c value wouldn t be needed if they were combined into two operations in sequence  Since you know you will do one then the other everytime  There s room for for some polish    This should be the most efficient way to do this  with time complexity of O log n  log i   rather than O n   And worst case time complexity of O n   If your arrays are clumpy and have long strings of values together  this will dwarf any other way to do it  otherwise it ll just be better than them   It has two read values at the ends of the merging array and the write value within the results array  After finding out which is end value is less  it does a gallop search into that array  1  2  4  8  16  32  etc  When it finds the range where the the other array s read value is bigger  It binary searches into that range  cuts the range in half  search the correct half  repeat until single value   Then it array copies those values into the write position  Keeping in mind that the copy is  by necessity  moved such that it cannot overwrite the same values from the either reading array  which means the write array and read array can be the same   It then performs the same operation for the other array which is now known to be less than the new read value of the other array   static public int gallopSearch int current  int   array  int v        int d   1      int seek   current - d      int prevIteration   seek      while  seek  gt  0            if  Integer compare array seek   v   lt   0                break                    prevIteration   seek          d  lt  lt   1          seek   current - d          if  seek  lt  0                seek   0                      if  prevIteration    seek            seek   binarySearch array  seek  prevIteration  v           seek   seek  gt   0   seek    seek            return seek     static public int binarySearch int   list  int fromIndex  int toIndex  int v        int low   fromIndex      int high   toIndex - 1      while  low  lt   high            int mid    low   high   gt  gt  gt  1          int midVal   list mid           int cmp   Integer compare midVal  v           if  cmp  lt  0                low   mid   1            else if  cmp  gt  0                high   mid - 1            else               return mid    key found                     return - low   1     key not found     static public int   sortedArrayMerge int   a  int   b        return sortedArrayMerge null  a  a length  b  b length      static public int   sortedArrayMerge int   results  int   a  int aRead  int b    int bRead        int write   aRead   bRead  length  gallopPos      if   results    null      results length  lt  write             results   new int write             if  aRead  gt  0  amp  amp  bRead  gt  0            int c   Integer compare a aRead - 1   b bRead - 1            while  aRead  gt  0  amp  amp  bRead  gt  0                switch  c                    default                      gallopPos   gallopSearch aRead  a  b bRead-1                        length    aRead - gallopPos                       write -  length                      aRead   gallopPos                      System arraycopy a  gallopPos--  results  write  length                       c   -1                      break                  case -1                      gallopPos   gallopSearch bRead  b  a aRead-1                        length    bRead - gallopPos                       write -  length                      bRead   gallopPos                      System arraycopy b  gallopPos--  results  write  length                       c   1                      break                                    if  bRead  gt  0            if  b    results                System arraycopy b  0  results  0  bRead                   else if  aRead  gt  0            if  a    results                System arraycopy a  0  results  0  aRead                       return results      This should be the most efficient way to do it     Some answers had a duplicate remove ability  That ll require an O n  algorithm because you must actually compare each item  So here s a stand-alone for that  to be applied after the fact  You can t gallop through multiple entries all the way through if you need to look at all of them  though you could gallop through the duplicates  if you had a lot of them   static public int removeDuplicates int   list  int size        int write   1      for  int read   1  read  lt  size  read              if  list read     list read - 1                 continue                    list write      list read             return write        Update  Previous answer  not horrible code but clearly inferior to the above   Another needless hyper-optimization  It not only invokes arraycopy for the end bits  but also for the beginning  Processing any introductory non-overlap in O log n   by a binarySearch into the data  O log n    n  is O n  and in some cases the effect will be pretty pronounced especially things like where there is no overlap between the merging arrays at all   private static int binarySearch int   array  int low  int high  int v        high   high - 1      while  low  lt   high            int mid    low   high   gt  gt  gt  1          int midVal   array mid           if  midVal  gt  v              low   mid   1          else if  midVal  lt  v              high   mid - 1          else             return mid     key found           return low   traditionally  - low   1       key not found     private static int   sortedArrayMerge int a    int b          int result     new int a length   b length       int k  i   0  j   0      if  a 0   gt  b 0             k   i   binarySearch b  0  b length  a 0            System arraycopy b  0  result  0  i         else           k   j   binarySearch a  0  a length  b 0            System arraycopy a  0  result  0  j             while  i  lt  a length  amp  amp  j  lt  b length            result k       a i   lt  b j     a i      b j               if  j  lt  b length            System arraycopy b  j  result  k   b length - j          else           System arraycopy a  i  result  k   a length - i              return result

User · Answer

Any improvements that could be made would be micro-optimizations  the overall algorithm is correct

User · Answer

A minor improvement  but after the main loop  you could use System arraycopy to copy the tail of either input array when you get to the end of the other  That won t change the O n  performance characteristics of your solution  though

User · Answer

Here is updated function  It removes duplicates  hopefully someone will find this usable   public static long   merge2SortedAndRemoveDublicates long   a  long   b        long   answer   new long a length   b length       int i   0  j   0  k   0      long tmp      while  i  lt  a length  amp  amp  j  lt  b length            tmp   a i   lt  b j    a i      b j             for     i  lt  a length  amp  amp  a i     tmp  i             for     j  lt  b length  amp  amp  b j     tmp  j             answer k      tmp            while  i  lt  a length            tmp   a i             for     i  lt  a length  amp  amp  a i     tmp  i             answer k      tmp            while  j  lt  b length            tmp   b j             for     j  lt  b length  amp  amp  b j     tmp  j             answer k      tmp            return Arrays copyOf answer  k

User · Answer

public static void main String   args        int   arr1    2 4 6 8 10 999       int   arr2    1 3 5 9 100 1001        int   arr3   new int arr1 length   arr2 length        int temp   0       for  int i   0  i  lt   arr3 length   i              if temp    arr2 length               arr3 i    arr1 i-temp                     else if    i-temp  lt  arr1 length    amp  amp   arr1 i-temp   lt  arr2 temp                     arr3 i    arr1 i-temp                     else              arr3 i    arr2 temp               temp                         for  int i   arr3            System out print i                    Output is    1  2  3  4  5  6  8  9  10  100  999  1001

User · Answer

public static int   merge int   a  int   b         int   answer   new int a length   b length       int i   0  j   0  k   0       while  i  lt  a length  amp  amp  j  lt  b length           answer k      a i   lt  b j    a i       b j          while  i  lt  a length            answer k      a i          while  j  lt  b length              answer k      b j          return answer      Is a little bit more compact but exactly the same

User · Answer

Algorithm could be enhanced in many ways  For instance  it is reasonable to check  if a m-1  lt b 0  or b n-1  lt a 0    In any of those cases  there is no need to do more comparisons   Algorithm could just copy source arrays in the resulting one in the right order   More complicated enhancements may include searching for interleaving parts and run merge algorithm for them only   It could save up much time  when sizes of merged arrays differ in scores of times

User · Answer

To marge two sorted array in O m n  time complexity use below approach with one loop only  m and n is length of first array and second array   public class MargeSortedArray       public static void main String   args            int   array   new int   1 3 4 7           int   array2   new int   2 5 6 8 12 45           int   newarry   margeToSortedArray array  array2             newarray is marged array               marge two sorted array with o a n  time complexity     public static int   margeToSortedArray int   array  int   array2            int newarrlen   array length array2 length          int   newarr   new int newarrlen            int pos1 0 pos2 0          int len1 array length  len2 array2 length           for int i  0 i lt newarrlen i                       if pos1 gt  len1                    newarr i  array2 pos2                   pos2                    continue                            if pos2 gt  len2                    newarr i  array pos1                   pos1                    continue                             if array pos1  gt array2 pos2                     newarr i  array2 pos2                   pos2                  else                   newarr i  array pos1                   pos1                                        return newarr

User · Answer

Since the question doesn t assume any specific language  Here is the solution in Python  Assuming the arrays are already sorted    Approach 1 - using numpy arrays      import numpy  arr1   numpy asarray   1   2   3   4   5   6   7   8   9  11  14  15  55   arr2   numpy asarray  11  32  43  45  66  76  88    array   numpy concatenate  arr1 arr2   axis 0  array sort     Approach 2 - Using list  assuming lists are sorted   list new   list1 extend list2  list new sort

User · Answer

Here s a shortened form written in javascript   function sort  a1  a2          var i   0           j   0           l1   a1 length           l2   a2 length           a            while  i  lt  l1  amp  amp  j  lt  l2              a1 i   lt  a2 j     a push a1 i    i       a push  a2 j    j                i  lt  l1  amp  amp    a   a concat  a1 splice i          j  lt  l2  amp  amp    a   a concat  a2 splice j           return a

User · Answer

import java util Arrays   public class MergeTwoArrays        static int   arr1 new int   1 3 4 5 7 7 9 11 13 15 17 19       static int   arr2 new int   2 4 6 8 10 12 14 14 16 18 20 22        public static void main String   args           int FirstArrayLocation  0           int SecondArrayLocation 0          int   mergeArr new int arr1 length   arr2 length            for   int i 0  i lt   arr1 length   arr2 length  i                 if    FirstArrayLocation  lt  arr1 length    amp  amp   SecondArrayLocation  lt  arr2 length                    if   arr1 FirstArrayLocation   lt   arr2 SecondArrayLocation                        mergeArr i  arr1 FirstArrayLocation                       FirstArrayLocation                     else                      mergeArr i  arr2 SecondArrayLocation                       SecondArrayLocation                                                else if SecondArrayLocation  lt  arr2 length                       mergeArr i  arr2 SecondArrayLocation                       SecondArrayLocation                 else if   FirstArrayLocation  lt  arr1 length                        mergeArr i  arr1 FirstArrayLocation                       FirstArrayLocation

User · Answer

var arr1    2 10 20 30 100   var arr2    2 4 5 6 7 8 9   var j   0  var i  0  var newArray        for var x 0 x lt   arr1 length   arr2 length  x         if arr1 i   gt   arr2 j                     check if element arr2 is equal and less than arr1 element         newArray push arr2 j          j         else if arr1 i   lt  arr2 j                 check if element arr1 index value  is less than arr2 element         newArray push arr1 i            i              else if i    arr1 length    j  lt  arr2 length         add remaining arr2 element         newArray push arr2 j            j        else                                                       add remaining arr1 element         newArray push arr1 i             i             console log newArray

User · Answer

My favorite programming language is JavaScript  function mergeSortedArrays a  b       var result            var sI   0      var lI   0      var smallArr      var largeArr      var temp       if typeof b 0       undefined     a 0  lt b 0            smallArr   a          largeArr   b        else          smallArr   b          largeArr   a             while typeof smallArr sI       undefined            result push smallArr sI            sI             if smallArr sI  gt largeArr lI     typeof smallArr sI       undefined                temp   smallArr              smallArr   largeArr              largeArr   temp              temp   sI              sI   lI              lI   temp                      return result

User · Answer

I had to write it in javascript  here it is   function merge a  b        var result           var ai   0      var bi   0      while  true            if   ai  lt  a length  amp  amp  bi  lt  b length                if  a ai   lt  b bi                     result push a ai                    ai                  else if  a ai   gt  b bi                     result push b bi                    bi                  else                   result push a ai                    result push b bi                    ai                    bi                            else if  ai  lt  a length                result push apply result  a slice ai  a length                break            else if  bi  lt  b length                result push apply result  b slice bi  b length                break            else               break                      return result

User · Answer

var arrCombo   function arr1  arr2     return arr1 concat arr2  sort function x  y        return x - y

User · Answer

Apache collections supports collate method since version 4  you can do this using the collate method in   org apache commons collections4 CollectionUtils   Here quote from javadoc    collate Iterable lt   extends O gt  a  Iterable lt   extends O gt  b  Comparator lt   super O gt  c        Merges two sorted Collections  a and b  into a single    sorted List such that the ordering of the elements according to   Comparator c is retained    Do not re-invent the wheel  Document reference  http   commons apache org proper commons-collections apidocs org apache commons collections4 CollectionUtils html

User · Answer

public int   merge int   a  int   b        int   result   new int a length   b length       int aIndex  bIndex   0       for  int i   0  i  lt  result length  i              if  aIndex  lt  a length  amp  amp  bIndex  lt  b length                if  a aIndex   lt  b bIndex                     result i    a aIndex                   aIndex                  else                   result i    b bIndex                   bIndex                            else if  aIndex  lt  a length                result i    a aIndex               aIndex              else               result i    b bIndex               bIndex                         return result

User · Answer

Here is my java implementation that remove duplicate    public static int   mergesort int   a  int   b        int   c   new int a length   b length       int i   0  j   0  k   0  duplicateCount   0       while  i  lt  a length    j  lt  b length            if  i  lt  a length  amp  amp  j  lt  b length                if  a i     b j                     c k    a i                   i   j   duplicateCount                  else                   c k    a i   lt  b j    a i      b j                             else if  i  lt  a length                c k    a i               else if  j  lt  a length                c k    b j                       k               return Arrays copyOf c  c length - duplicateCount

User · Answer

public class Merge           stably merge a lo    mid  with a mid 1    hi  using aux lo    hi      public static void merge Comparable   a  Comparable   aux  int lo  int mid  int hi                precondition  a lo    mid  and a mid 1    hi  are sorted subarrays         assert isSorted a  lo  mid           assert isSorted a  mid 1  hi               copy to aux           for  int k   lo  k  lt   hi  k                  aux k    a k                          merge back to a           int i   lo  j   mid 1          for  int k   lo  k  lt   hi  k                  if       i  gt  mid               a k    aux j                 else if  j  gt  hi                a k    aux i                 else if  less aux j   aux i    a k    aux j                 else                           a k    aux i                           postcondition  a lo    hi  is sorted         assert isSorted a  lo  hi                 mergesort a lo  hi  using auxiliary array aux lo  hi      private static void sort Comparable   a  Comparable   aux  int lo  int hi            if  hi  lt   lo  return          int mid   lo    hi - lo    2          sort a  aux  lo  mid           sort a  aux  mid   1  hi           merge a  aux  lo  mid  hi              public static void sort Comparable   a            Comparable   aux   new Comparable a length           sort a  aux  0  a length-1           assert isSorted a                                                                                              Helper sorting functions                                                                                      is v  lt  w       private static boolean less Comparable v  Comparable w            return  v compareTo w   lt  0                 exchange a i  and a j      private static void exch Object   a  int i  int j            Object swap   a i           a i    a j           a j    swap                                                                                             Check if array is sorted - useful for debugging                                                                                  private static boolean isSorted Comparable   a            return isSorted a  0  a length - 1              private static boolean isSorted Comparable   a  int lo  int hi            for  int i   lo   1  i  lt   hi  i                if  less a i   a i-1    return false          return true                                                                                             Index mergesort                                                                                     stably merge a lo    mid  with a mid 1    hi  using aux lo    hi      private static void merge Comparable   a  int   index  int   aux  int lo  int mid  int hi                copy to aux           for  int k   lo  k  lt   hi  k                  aux k    index k                          merge back to a           int i   lo  j   mid 1          for  int k   lo  k  lt   hi  k                  if       i  gt  mid                     index k    aux j                 else if  j  gt  hi                      index k    aux i                 else if  less a aux j    a aux i     index k    aux j                 else                                 index k    aux i                             return a permutation that gives the elements in a   in ascending order        do not change the original array a       public static int   indexSort Comparable   a            int N   a length          int   index   new int N           for  int i   0  i  lt  N  i                index i    i           int   aux   new int N           sort a  index  aux  0  N-1           return index                mergesort a lo  hi  using auxiliary array aux lo  hi      private static void sort Comparable   a  int   index  int   aux  int lo  int hi            if  hi  lt   lo  return          int mid   lo    hi - lo    2          sort a  index  aux  lo  mid           sort a  index  aux  mid   1  hi           merge a  index  aux  lo  mid  hi                 print array to standard output     private static void show Comparable   a            for  int i   0  i  lt  a length  i                  StdOut println a i                            Read strings from standard input  sort them  and print      public static void main String   args            String   a   StdIn readStrings            Merge sort a           show a

User · Answer

This problem is related to the mergesort algorithm  in which two sorted sub-arrays are combined into a single sorted sub-array  The CLRS book gives an example of the algorithm and cleans up the need for checking if the end has been reached by adding a sentinel value  something that compares and  greater than any other value   to the end of each array   I wrote this in Python  but it should translate nicely to Java too   def func a  b       class sentinel object           def   lt                    return False      ax  bx  c   a       sentinel     b       sentinel            i  j   0  0      for k in range len a    len b            if ax i   lt  bx j               c append ax i               i    1         else              c append bx j               j    1      return c

User · Answer

public static int   merge int   listA  int   listB            int   mergedList   new int  listA length   listB length           int i   0     Counter for listA         int j   0     Counter for listB         int k   0     Counter for mergedList         while  true                if  i  gt   listA length  amp  amp  j  gt   listB length                    break                            if  i  lt  listA length  amp  amp  j  lt  listB length       If both counters are valid                  if  listA i   lt   listB j                         mergedList k    listA i                       k                        i                      else                       mergedList k    listB j                       k                        j                                    else if  i  lt  listA length  amp  amp  j  gt   listB length       If only A s counter is valid                  mergedList k    listA i                   k                    i                  else if  i  lt   listA length  amp  amp  j  lt  listB length       If only B s counter is valid                 mergedList k    listB j                   k                    j                                    return mergedList

User · Answer

I m surprised no one has mentioned this much more cool  efficient and compact implementation   public static int   merge int   a  int   b        int   answer   new int a length   b length       int i   a length - 1  j   b length - 1  k   answer length       while  k  gt  0          answer --k                     j  lt  0     i  gt   0  amp  amp  a i   gt   b j      a i--    b j--       return answer      Points of Interests   Notice that it does same or less number of operations as any other O n  algorithm but in literally single statement in a single while loop   If two arrays are of approximately same size then constant for O n  is same  However if arrays are really imbalanced then versions with System arraycopy would win because internally it can do this with single x86 assembly instruction  Notice a i   gt   b j  instead of a i   gt  b j   This guarantees  stability  that is defined as when elements of a and b are equal  we want elements from a before b

User · Answer

You could use 2 threads to fill the resulting array  one from front  one from back   This can work without any synchronization in the case of numbers  e g  if each thread inserts half of the values

User · Answer

Maybe use System arraycopy  public static byte   merge byte   first  byte   second       int len   first length   second length      byte   full   new byte len       System arraycopy first  0  full  0  first length       System arraycopy second  0  full  first length  second length       return full

User · Answer

This solution also very similar to other posts except that it uses System arrayCopy to copy the remaining array elements   private static int   sortedArrayMerge int a    int b          int result     new int a length  b length       int i  0  int j   0 int k   0      while i lt a length  amp  amp  j  lt b length            if a i  lt b j                 result k      a i               i              else               result k      b j               j                        System arraycopy a  i  result  k   a length -i        System arraycopy b  j  result  k   b length -j        return result

User · Answer

How to merge two sorted arrays into a sorted array without duplicates    simple C Coding  include  lt stdio h gt   include  lt stdlib h gt   include  lt string h gt   main         int InputArray1     1 4 5 7 8 9 12 13 14 17 40       int InputArray2     4 5 11 14 15 17 18 19 112 122 122 122 122       int n 10      int OutputArray 30       int i 0 j 0 k 0        k OutputArray     while i lt 11  amp  amp  j lt 13                if InputArray1 i  lt InputArray2 j                         if  k    0    InputArray1 i    OutputArray k-1                                 OutputArray k      InputArray1 i                             i i 1                    else if InputArray1 i  gt InputArray2 j                         if  k    0    InputArray2 j    OutputArray k-1                                 OutputArray k      InputArray2 j                             j j 1                    else                       if  k    0    InputArray1 i    OutputArray k-1                                 OutputArray k      InputArray1 i                             i i 1              j j 1                       while i lt 11                if InputArray1 i    OutputArray k-1               OutputArray k      InputArray1 i             else             i              while j lt 13                if InputArray2 j    OutputArray k-1               OutputArray k      InputArray2 j             else             j              for i 0  i lt k  i                  printf  sorted data  d n  OutputArray i

User · Answer

I think introducing the skip list for the larger sorted array can reduce the number of comparisons and can speed up the process of copying into the third array  This can be good if the array is too huge

User · Answer

public static int   merge int   a  int   b        int   mergedArray   new int  a length   b length        int i   0  j   0      int mergedArrayIndex   0      for    i  lt  a length    j  lt  b length             if  i  lt  a length  amp  amp  j  lt  b length                if  a i   lt  b j                     mergedArray mergedArrayIndex    a i                   i                  else                   mergedArray mergedArrayIndex    b j                   j                            else if  i  lt  a length                mergedArray mergedArrayIndex    a i               i              else if  j  lt  b length                mergedArray mergedArrayIndex    b j               j                      mergedArrayIndex              return mergedArray

User · Answer

It can be done in 4 statements as below   int a      10  20  30    int b     9  14  11    int res   new int a legth b length     System arraycopy a 0  res  0  a length     System arraycopy b 0 res a length  b length    Array sort res

[java] How to merge two sorted arrays into a sorted array?

Examples related to java

Examples related to algorithm

Examples related to big-o

Examples related to mergesort