Merge sort

README.md

Merge sort implementations in python and coffeescript.

index.coffee

# Divide an array into two sub-arrays
split = (arr) ->
  n = arr.length - 1
  i = Math.round(n / 2)
  [arr[...i], arr[i..]]

# Merge two sorted sub-arrays
merge = (a, b) ->
  n = a.length + b.length
  i = j = 0
  result = []
  for k in [0..n]
    if a[i] < b[j]
      result.push(a[i])
      i += 1
    else
      result.push(b[j])
      j += 1
    if a.length == i
      return result.concat(b[j..])
    else if b.length == j
      return result.concat(a[i..])
  result
  
# Numerically sort an array
sort = (arr) ->
    return arr if arr.length < 2
    [a, b] = split(arr)
    merge(sort(a), sort(b))


# Testing
assert = require 'assert'

input = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

assert.deepEqual sort(input), input.reverse()

index.py

import random


def split(arr):
    '''
    Divide an array into two sub-arrays.

    '''
    n = len(arr)
    i = n / 2
    a, b = arr[:i], arr[i:]
    return a, b


def _merge(a, b, result=[]):
    '''
    Merge two sorted subarrays.

    This is a recursive variant of `merge`.  
    Problematic/inefficient on large input.

    '''
    if not a:
        return result + b
    if not b:
        return result + a
    if a[0] < b[0]:
        return merge(a[1:], b, result + a[:1])
    else:
        return merge(a, b[1:], result + b[:1])
  

def merge(a, b):
    '''
    Merge two sorted sub-arrays.

    '''
    i = j = 0
    result = []
    for k in range(len(a) + len(b)):
        if a[i] < b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
        if len(a) == i:
            result.extend(b[j:])
            break
        elif len(b) == j:
            result.extend(a[i:])
            break
    return result


def sort(arr):
    '''
    Numerically sort an array.

    '''
    if len(arr) < 2: return arr
    a, b = split(arr)
    return merge(sort(a), sort(b))


# Testing
n = 1000
input = range(n)
random.shuffle(input)

assert sort(input) == range(n)