How does one iteratively write merge sort?

Question

I have written a recursive version of merge sort. It makes use of a separate merge routine:

Click to copy

def merge(lst1, lst2):
    i = j = 0
    merged = []
    while i < len(lst1) and j < len(lst2):
        if lst1[i] <= lst2[j]:
            merged.append(lst1[i])
            i += 1
        else:
            merged.append(lst2[j])
            j += 1
    merged.extend(lst1[i:])
    merged.extend(lst2[j:])
    return merged

def merge_sort(lst):
    if len(lst) < 2:
        return lst
    else:
        middle = len(lst) / 2
        return merge(merge_sort(lst[:middle]), merge_sort(lst[middle:]))

To conserve stack space (and for kicks/the sheer joy of learning algorithms), I am trying to write this function in an iterative manner. However, I find this difficult because I am not sure how to combine disparate lists in the very end.

Thank you!

Answer 1

You will need a merge function (the same or almost same merge function) which will be called repeatedly. So, you don't need to change the merge function.

This is a multiple pass solution. Start with a chunk size of 2 and double the chunk size in every pass.

In every pass, partition the list into non-overlapping chunks of size whatever. Split every chunk into 2 and call merge on the 2 parts.

This is a bottom up version.

Answer 2

I expanded based on Divya's description (added a test function for verification as well). The below code may be optimized by eliminating sub-arrays(data_1 and data_2) and sorting in place.

Click to copy

def merge_sort_iterative(data):
  """ gets the data using merge sort and returns sorted."""

  for j in range(1, len(data)):
    j *= 2
    for i in range(0,len(data),j):
      data_1 = data[i:i+(j/2)]
      data_2 = data[i+(j/2):j-i]
      l = m = 0
      while l < len(data_1) and m < len(data_2):
        if data_1[l] < data_2[m]:
          m += 1
        elif data_1[l] > data_2[m]:
          data_1[l], data_2[m] = data_2[m], data_1[l]
          l += 1
      data[i:i+(j/2)], data[i+(j/2):j-i] = data_1, data_2

  return data

def test_merge_sort():
  """test function for verifying algorithm correctness"""

  import random
  import time

  sample_size = 5000
  sample_data = random.sample(range(sample_size*5), sample_size)
  print 'Sample size: ', sample_size

  begin = time.time()
  sample_data = [5,4,3,2,1]
  result = merge_sort_iterative(sample_data)
  end = time.time()
  expected = sorted(sample_data)
  print 'Sorting time: %f \'secs'%(end-begin)

  assert result == expected, 'Algorithm failed'
  print 'Algorithm correct'

if __name__ == '__main__':
  test_merge_sort()

Answer 3

Here is Java Implementation

Click to copy

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}

public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

Here is the unit test

Click to copy

private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}