Merge two sorted arrays with no extra space. However, this runs in O(n^2) time.

merge.py

#!/usr/bin/python

import random
try:
  from termcolor import colored
except ImportError:
  def colored(s, color):
    return s

ERROR = 0
DEBUG = 1
INFO = 2


class Sorter:
  def __init__(self, debug_level=ERROR, min_length=5, max_length=10):
    self.array_length = random.randint(min_length, max_length)
    self.a = sorted([random.randint(0, 50) for x in range(self.array_length)])
    self.b = sorted([random.randint(0, 50) for x in range(self.array_length)])
    self.array = self.a + self.b

    self.pa = 0
    self.pb = self.array_length
    self.swap_start = -1
    self.swap_end = -1
    self.debug_lvl = debug_level

    def my_print(s, n=INFO):
      if n <= self.debug_lvl:
        print s

    def print_dummy(s, n=INFO):
      pass

    if debug_level > 0:
      self.debug = my_print
    else:
      self.debug = print_dummy

  def format_array(self):
    out = "["
    for i in range(len(self.array)):
      if self.pa <= i < self.pb and (self.swap_start < 0 or i < self.swap_start):
        out += colored("%2d" % self.array[i], 'green')
      elif i >= self.pb:
        out += colored("%2d" % self.array[i], 'yellow')
      elif self.swap_start <= i <= self.swap_end:
        out += colored("%2d" % self.array[i], 'blue')
      else:
        out += "%2d" % self.array[i]

      if i < len(self.array) - 1:
        out += ", "
    return out + "]"

  def sort_array(self):
    while (self.pa < self.array_length or self.pb < 2 * self.array_length) and self.swap_start < 2 * self.array_length:
      self.debug("pa=%2d, pb=%2d, swap_start=%2d, swap_end=%2d: %s" % (
        self.pa, self.pb, self.swap_start, self.swap_end, self.format_array()), DEBUG)

      if self.swap_start != -1:
        self.debug("\t with swap space")
        if self.pa < self.array_length:
          self.debug("\t pa has values")
          if self.array[self.swap_start] <= self.array[self.pb]:
            self.array[self.pa], temp = self.array[self.swap_start], self.array[self.pa]
            self.pa += 1
            for i in range(self.swap_start, self.swap_end):
              self.debug("\t shifting forward from %d to %d" % (i + 1, i))
              self.array[i] = self.array[i + 1]
            self.array[self.swap_end] = temp

          else:
            self.array[self.pa], self.array[self.pb] = self.array[self.pb], self.array[self.pa]
            self.swap_end += 1
            self.pa += 1
            self.pb += 1
        else:
          self.debug("\t pa is empty")
          if self.array[self.swap_start] <= self.array[self.pb]:
            self.swap_start += 1
            self.pa += 1

          else:
            temp = self.array[self.pb]
            for i in range(self.swap_end, self.swap_start - 1, -1):
              self.debug("\t shifting backward from %d to %d" % (i, i + 1))
              self.array[i + 1] = self.array[i]
            self.array[self.swap_start] = temp
            self.swap_end += 1
            self.swap_start += 1
            self.pa += 1
            self.pb += 1

      else:
        self.debug("\t without swap space")
        if self.array[self.pa] <= self.array[self.pb]:
          self.pa += 1
        else:
          self.array[self.pa], self.array[self.pb] = self.array[self.pb], self.array[self.pa]
          self.swap_start = self.swap_end = self.pb
          self.pa += 1
          self.pb += 1

    self.debug("pa=%2d, pb=%2d, swap_start=%2d, swap_end=%2d: %s" % (
        self.pa, self.pb, self.swap_start, self.swap_end, self.format_array()), DEBUG)


for i in range(1000):
  s = Sorter()
  s.sort_array()

  #print
  if s.array != sorted(s.array):
    print "\t !! ERROR !!"
  #print self.array
  #

s = Sorter(debug_level=DEBUG, max_length=6)
s.sort_array()