Como mesclar duas matrizes ordenadas em uma matriz ordenada?

Isso me foi solicitado em uma entrevista e esta é a solução que eu forneci:

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 < a.length && j < b.length) { if (a[i] < b[j]) { answer[k] = a[i]; i++; } else { answer[k] = b[j]; j++; } k++; } while (i < a.length) { answer[k] = a[i]; i++; k++; } while (j < b.length) { answer[k] = b[j]; j++; k++; } return answer; } 

Existe uma maneira mais eficiente de fazer isso?

Edit: methods de comprimento corrigidos.

Um pequeno aprimoramento, mas após o loop principal, você poderia usar System.arraycopy para copiar a cauda de qualquer array de input quando chegar ao final do outro. Isso não mudará as características de desempenho O(n) de sua solução, no entanto.

 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 < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; while (i < a.length) answer[k++] = a[i++]; while (j < b.length) answer[k++] = b[j++]; return answer; } 

É um pouco mais compacto mas exatamente igual!

Estou surpreso que ninguém tenha mencionado essa implementação muito mais legal, eficiente e compacta:

 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 > 0) answer[--k] = (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--]; return answer; } 

Pontos de Interesse

  1. Observe que ele faz o mesmo ou menos número de operações que qualquer outro algoritmo O (n) , mas na instrução literalmente única em um único loop while!
  2. Se duas matrizes são aproximadamente do mesmo tamanho, então constante para O (n) é a mesma. No entanto, se os arrays forem realmente desbalanceados, as versões com System.arraycopy serão System.arraycopy porque internamente ele poderá fazer isso com instruções de assembly x86 individuais.
  3. Observe a[i] >= b[j] vez de a[i] > b[j] . Isso garante a “estabilidade” que é definida como quando os elementos de a e b são iguais, queremos elementos de um antes b.

Quaisquer melhorias que poderiam ser feitas seriam micro-otimizações, o algoritmo geral está correto.

Essa solução também é muito semelhante a outros posts, exceto pelo fato de usar System.arrayCopy para copiar os elementos de matriz restantes.

 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 

Aqui está a function atualizada. Ele remove duplicatas, esperamos que alguém ache isso útil:

 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 < a.length && j < b.length) { tmp = a[i] < b[j] ? a[i++] : b[j++]; for ( ; i < a.length && a[i] == tmp; i++); for ( ; j < b.length && b[j] == tmp; j++); answer[k++] = tmp; } while (i < a.length) { tmp = a[i++]; for ( ; i < a.length && a[i] == tmp; i++); answer[k++] = tmp; } while (j < b.length) { tmp = b[j++]; for ( ; j < b.length && b[j] == tmp; j++); answer[k++] = tmp; } return Arrays.copyOf(answer, k); } 

Isso pode ser feito em 4 declarações como abaixo

  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) 

Eu tive que escrevê-lo em javascript, aqui está:

 function merge(a, b) { var result = []; var ai = 0; var bi = 0; while (true) { if ( ai < a.length && bi < b.length) { if (a[ai] < b[bi]) { result.push(a[ai]); ai++; } else if (a[ai] > b[bi]) { result.push(b[bi]); bi++; } else { result.push(a[ai]); result.push(b[bi]); ai++; bi++; } } else if (ai < a.length) { result.push.apply(result, a.slice(ai, a.length)); break; } else if (bi < b.length) { result.push.apply(result, b.slice(bi, b.length)); break; } else { break; } } return result; } 

Coleções do Apache suportam o método collate desde a versão 4; você pode fazer isso usando o método collate em:

 org.apache.commons.collections4.CollectionUtils 

Aqui citações do javadoc:

 collate(Iterable a, Iterable b, Comparator c) 

Mescla duas collections ordenadas, b , em uma única lista classificada, de modo que a ordenação dos elementos de acordo com o Comparador c seja mantida.

Não reinvente a roda! Referência do documento: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

Aqui está um formulário abreviado escrito em javascript:

 function sort( a1, a2 ) { var i = 0 , j = 0 , l1 = a1.length , l2 = a2.length , a = []; while( i < l1 && j < l2 ) { a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++); } i < l1 && ( a = a.concat( a1.splice(i) )); j < l2 && ( a = a.concat( a2.splice(j) )); return a; } 
  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 <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > 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 <= 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 < w ? private static boolean less(Comparable v, Comparable w) { return (v.compareTo(w) < 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 <= 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 <= hi; k++) { aux[k] = index[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) index[k] = aux[j++]; else if (j > 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 < 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 <= 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 < 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); } } 

Eu acho que a introdução da lista de pulos para o array ordenado maior pode reduzir o número de comparações e acelerar o processo de cópia no terceiro array. Isso pode ser bom se o array for muito grande.

 public int[] merge(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int aIndex, bIndex = 0; for (int i = 0; i < result.length; i++) { if (aIndex < a.length && bIndex < b.length) { if (a[aIndex] < b[bIndex]) { result[i] = a[aIndex]; aIndex++; } else { result[i] = b[bIndex]; bIndex++; } } else if (aIndex < a.length) { result[i] = a[aIndex]; aIndex++; } else { result[i] = b[bIndex]; bIndex++; } } return result; } 
 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 < a.length || j < b.length;) { if (i < a.length && j < b.length) { if (a[i] < b[j]) { mergedArray[mergedArrayIndex] = a[i]; i++; } else { mergedArray[mergedArrayIndex] = b[j]; j++; } } else if (i < a.length) { mergedArray[mergedArrayIndex] = a[i]; i++; } else if (j < b.length) { mergedArray[mergedArrayIndex] = b[j]; j++; } mergedArrayIndex++; } return mergedArray; } 

Algoritmo pode ser aprimorado de várias maneiras. Por exemplo, é razoável verificar, se a[m-1] ou b[n-1] . Em qualquer um desses casos, não há necessidade de fazer mais comparações. Algoritmo poderia apenas copiar matrizes de origem na ordem resultante.

Melhorias mais complicadas podem include a busca por intercalar partes e executar o algoritmo de mesclagem somente para elas. Pode economizar muito tempo, quando os tamanhos das matrizes mescladas diferem em dezenas de vezes.

Esse problema está relacionado ao algoritmo mergesort, no qual duas sub-matrizes ordenadas são combinadas em uma única sub-matriz classificada. O livro CLRS dá um exemplo do algoritmo e limpa a necessidade de verificar se o fim foi alcançado, adicionando um valor de sentinela (algo que compara e “maior que qualquer outro valor”) ao final de cada matriz.

Eu escrevi isso em Python, mas ele deve se traduzir bem em Java também:

 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] < bx[j]: c.append(ax[i]) i += 1 else: c.append(bx[j]) j += 1 return c 

Você poderia usar 2 threads para preencher a matriz resultante, um da frente, um da parte de trás.

Isso pode funcionar sem qualquer synchronization no caso de números, por exemplo, se cada thread inserir metade dos valores.

Fusão GallopSearch: O (log (n) * log (i)) ao invés de O (n)

Eu fui em frente e implementei sugestão de barba grisalha nos comentários. Principalmente porque eu precisava de uma versão de missão crítica altamente eficiente desse código.

  • O código usa um gallopSearch que é O (log (i)) onde i é a distância do índice atual que o índice relevante existe.
  • O código usa um binarySearch para depois que a pesquisa de galope identificou o intervalo adequado. Como o galope limitou isso a um intervalo menor, o resultado binarySearch também é O (log (i))
  • O galope e a fusão são realizados de trás para frente. Isso não parece essencial, mas permite a fusão de matrizes. Se uma de suas matrizes tiver espaço suficiente para armazenar os valores dos resultados, você poderá simplesmente usá-la como a matriz de mesclagem e a matriz de resultados. Você deve especificar o intervalo válido dentro do array em tal caso.
  • Não requer alocação de memory nesse caso (grandes economias em operações críticas). Ele simplesmente garante que não substitua e não possa sobrescrever quaisquer valores não processados ​​(o que só pode ser feito de trás para frente). Na verdade, você usa o mesmo array para as inputs e os resultados. Não sofrerá nenhum efeito negativo.
  • Eu usei consistentemente Integer.compare () para que isso pudesse ser alterado para outros fins.
  • Há alguma chance de eu ter brincado um pouco e não ter usado informações que eu já provei anteriormente. Como pesquisa binária em um intervalo de dois valores, para o qual um valor já foi verificado. Também pode haver uma maneira melhor de declarar o loop principal, o valor flipping c não seria necessário se eles fossem combinados em duas operações em seqüência. Desde que você sabe que você vai fazer um, então o outro toda vez. Há espaço para algum polimento.

Essa deve ser a maneira mais eficiente de fazer isso, com complexidade de tempo de O (log (n) * log (i)) em vez de O (n). E pior complexidade do tempo do caso de O (n). Se seus arrays forem complicados e tiverem longas cadeias de valores juntas, isso diminuirá qualquer outra maneira de fazê-lo, caso contrário, será melhor do que eles.

Ele possui dois valores de leitura nas extremidades da matriz de mesclagem e o valor de gravação na matriz de resultados. Depois de descobrir qual é o valor final é menor, ele faz uma pesquisa em galope nesse array. 1, 2, 4, 8, 16, 32, etc. Quando encontra o intervalo em que o valor de leitura da outra matriz é maior. Ele binário procura nesse intervalo (corta o intervalo ao meio, pesquisa a metade correta, repita até um único valor). Então, o array copia esses valores para a posição de gravação. Tendo em mente que a cópia é, por necessidade, movida de forma que ela não possa sobrescrever os mesmos valores da matriz de leitura (o que significa que a matriz de escrita e a matriz de leitura podem ser as mesmas). Em seguida, ele executa a mesma operação para o outro array que agora é conhecido como menor que o novo valor de leitura do outro array.

 static public int gallopSearch(int current, int[] array, int v) { int d = 1; int seek = current - d; int prevIteration = seek; while (seek > 0) { if (Integer.compare(array[seek], v) <= 0) { break; } prevIteration = seek; d <<= 1; seek = current - d; if (seek < 0) { seek = 0; } } if (prevIteration != seek) { seek = binarySearch(array, seek, prevIteration, v); seek = seek >= 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 <= high) { int mid = (low + high) >>> 1; int midVal = list[mid]; int cmp = Integer.compare(midVal, v); if (cmp < 0) { low = mid + 1; } else if (cmp > 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 < write)) { results = new int[write]; } if (aRead > 0 && bRead > 0) { int c = Integer.compare(a[aRead - 1], b[bRead - 1]); while (aRead > 0 && bRead > 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 > 0) { if (b != results) { System.arraycopy(b, 0, results, 0, bRead); } } else if (aRead > 0) { if (a != results) { System.arraycopy(a, 0, results, 0, aRead); } } return results; } 

Essa deve ser a maneira mais eficiente de fazer isso.


Algumas respostas tiveram uma capacidade de remoção duplicada. Isso exigirá um algoritmo O (n) porque você deve realmente comparar cada item. Então aqui está um autônomo para isso, para ser aplicado após o fato. Você não pode galopar através de múltiplas inputs até o fim, se você precisar olhar para todas elas, embora você possa galopar pelas duplicatas, se você tivesse muitas delas.

 static public int removeDuplicates(int[] list, int size) { int write = 1; for (int read = 1; read < size; read++) { if (list[read] == list[read - 1]) { continue; } list[write++] = list[read]; } return write; } 

Atualização: resposta anterior, código não horrível, mas claramente inferior ao acima.

Outra hiper-otimização desnecessária. Não só invoca arraycopy para os bits finais, mas também para o começo. Processamento de qualquer não-sobreposição introdutória em O (log (n)) por um binarySearch nos dados. O (log (n) + n) é O (n) e, em alguns casos, o efeito será bastante pronunciado, especialmente coisas como onde não há sobreposição entre as matrizes de mesclagem.

 private static int binarySearch(int[] array, int low, int high, int v) { high = high - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = array[mid]; if (midVal > v) low = mid + 1; else if (midVal < 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] > 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 < a.length && j < b.length) { result[k++] = (a[i] < b[j]) ? a[i++] : b[j++]; } if (j < b.length) { System.arraycopy(b, j, result, k, (b.length - j)); } else { System.arraycopy(a, i, result, k, (a.length - i)); } return result; } 
 //How to merge two sorted arrays into a sorted array without duplicates? //simple C Coding #include  #include  #include  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<11 && j<13) { if(InputArray1[i]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<11) { if(InputArray1[i]!= OutputArray[k-1]) OutputArray[k++] = InputArray1[i++]; else i++; } while(j<13) { if(InputArray2[j]!= OutputArray[k-1]) OutputArray[k++] = InputArray2[j++]; else j++; } for(i=0; i 
 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 >= listA.length && j >= listB.length) { break; } if (i < listA.length && j < listB.length) { // If both counters are valid. if (listA[i] <= listB[j]) { mergedList[k] = listA[i]; k++; i++; } else { mergedList[k] = listB[j]; k++; j++; } } else if (i < listA.length && j >= listB.length) { // If only A's counter is valid. mergedList[k] = listA[i]; k++; i++; } else if (i <= listA.length && j < listB.length) { // If only B's counter is valid mergedList[k] = listB[j]; k++; j++; } } return mergedList; } 
 var arrCombo = function(arr1, arr2){ return arr1.concat(arr2).sort(function(x, y) { return x - y; }); }; 

Minha linguagem de programação favorita é 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]largeArr[lI] || typeof smallArr[sI] === 'undefined'){ temp = smallArr; smallArr = largeArr; largeArr = temp; temp = sI; sI = lI; lI = temp; } } return result; } 

Talvez 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; } 
 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 < (arr3.length); i++) { if(temp == arr2.length){ arr3[i] = arr1[i-temp]; } else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){ arr3[i] = arr1[i-temp]; } else{ arr3[i] = arr2[temp]; temp++; } } for (int i : arr3) { System.out.print(i + ", "); } } 

A saída é:

1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,

Você pode usar operadores ternários para tornar o código um pouco mais compacto

 public static int[] mergeArrays(int[] a1, int[] a2) { int[] res = new int[a1.length + a2.length]; int i = 0, j = 0; while (i < a1.length && j < a2.length) { res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++]; } while (i < a1.length) { res[i + j] = a1[i++]; } while (j < a2.length) { res[i + j] = a2[j++]; } return res; } 
 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 < merged.length; i++) { if (nextIndexLeft >= left.length) { System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight); break; } if (nextIndexRight >= right.length) { System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft); break; } if (left[nextIndexLeft] <= right[nextIndexRight]) { merged[i] = left[nextIndexLeft]; nextIndexLeft++; continue; } if (left[nextIndexLeft] > right[nextIndexRight]) { merged[i] = right[nextIndexRight]; nextIndexRight++; continue; } } System.out.println("merged : " + Arrays.toString(merged)); return merged; } 

Apenas um pouco diferente da solução original

Para unir dois vetores ordenados em complexidade de tempo O (m + n), use a abordagem abaixo com apenas um loop. m e n é o comprimento da primeira matriz e da segunda matriz.

 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=len1) { newarr[i]=array2[pos2]; pos2++; continue; } if(pos2>=len2) { newarr[i]=array[pos1]; pos1++; continue; } if(array[pos1]>array2[pos2]) { newarr[i]=array2[pos2]; pos2++; } else { newarr[i]=array[pos1]; pos1++; } } return newarr; } } 
 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< (arr1.length + arr2.length);x++){ if(arr1[i] >= arr2[j]){ //check if element arr2 is equal and less than arr1 element newArray.push(arr2[j]); j++; }else if(arr1[i] < arr2[j]){ //check if element arr1 index value is less than arr2 element newArray.push(arr1[i]); i++; } else if(i == arr1.length || j < arr2.length){ // add remaining arr2 element newArray.push(arr2[j]); j++ }else{ // add remaining arr1 element newArray.push(arr1[i]); i++ } } console.log(newArray); 

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() 

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 < a.length || j < b.length) { if (i < a.length && j < b.length) { if (a[i] == b[j]) { c[k] = a[i]; i++;j++;duplicateCount++; } else { c[k] = a[i] < b[j] ? a[i++] : b[j++]; } } else if (i < a.length) { c[k] = a[i++]; } else if (j < a.length) { c[k] = b[j++]; } k++; } return Arrays.copyOf(c, c.length - duplicateCount); }