Ytl's Java Blog

厚积而薄发---每一天都是一个全新的开始
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Algorithm to merge sorted arrays

Posted on 2011-05-06 16:55 ytl 阅读(282) 评论(0)  编辑  收藏 所属分类: Algorithms and programming concepts

Algorithm to merge sorted arrays

In the article we present an algorithm for merging two sorted arrays. One can learn how to operate with several arrays and master read/write indices. Also, the algorithm has certain applications in practice, for instance in merge sort.

Merge algorithm

Assume, that both arrays are sorted in ascending order and we want resulting array to maintain the same order. Algorithm to merge two arrays A[0..m-1] and B[0..n-1] into an array C[0..m+n-1] is as following:

  1. Introduce read-indices ij to traverse arrays A and B, accordingly. Introduce write-index k to store position of the first free cell in the resulting array. By default i = j = k = 0.
  2. At each step: if both indices are in range (i < m and j < n), choose minimum of (A[i], B[j]) and write it toC[k]. Otherwise go to step 4.
  3. Increase k and index of the array, algorithm located minimal value at, by one. Repeat step 2.
  4. Copy the rest values from the array, which index is still in range, to the resulting array.

Enhancements

Algorithm could be enhanced in many ways. For instance, it is reasonable to check, if A[m - 1] < B[0] orB[n - 1] < 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.

Complexity analysis

Merge algorithm's time complexity is O(n + m). Additionally, it requires O(n + m) additional space to store resulting array.

Code snippets

Java implementation

// size of C array must be equal or greater than

// sum of A and B arrays' sizes

public void merge(int[] A, int[] B, int[] C) {

      int i,j,k ;

      i = 0;

      j=0;

      k=0;

      m = A.length;

      n = B.length;

      while(i < m && j < n){

          if(A[i]<= B[j]){

              C[k] = A[i];

              i++;

          }else{

              C[k] = B[j];

              j++;

       }

       k++;

       while(i<m){

         C[k] = A[i]

         i++;

         k++;

      }

      while(j<n){

         C[k] = B[j] 

         j++;

          k++;

 }


Python  implementation

def merege(left,right):

    result = []

    i,j = 0

   while i< len(left) and j < len(right):

        if left[i]<= right[j]:

            result.append(left[i])

            i = i + 1

        else:

            result.append(right[j])

            j = j + 1

    while i< len(left):

           result.append(left[i])

           i = i + 1

    while j< len(right):

           result.append(right[j])

           j = j + 1

    return result

  
MergSort:

import operator

def mergeSort(L, compare = operator.lt):
     if len(L) < 2:
          return L[:]
     else:
          middle = int(len(L)/2)
          left = mergeSort(L[:middle], compare)
          right= mergeSort(L[middle:], compare)
          return merge(left, right, compare)

def merge(left, right, compare):
     result = []
     i, j = 0, 0

     while i < len(left) and j < len(right):
          if compare(left[i], right[j]):
               result.append(left[i])
               i += 1
          else:
                result.append(right[j])
                j += 1
     while i < len(left):
          result.append(left[i])
          i += 1
     while j < len(right):
          result.append(right[j])
          j += 1
     return result