{
 "metadata": {
  "name": "",
  "signature": "sha256:58f9b9f1e695bd4bd45d59ca43938d3afa4ede22203e723d087d58f60b8af15b"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "MergeSort"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A less basic sorting algorithm that splits a sequence in two, then orders them splits..."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def mergesort(seq):\n",
      "    mid = len(seq)//2\n",
      "    lft, rgt = seq[:mid],seq[mid:]\n",
      "    if len(lft) > 1:\n",
      "        lft = mergesort(lft)\n",
      "    if len(rgt) > 1:\n",
      "        rgt = mergesort(rgt)\n",
      "    res =[]\n",
      "    while lft and rgt:\n",
      "        if lft[-1] > rgt[-1]:\n",
      "            res.append(lft.pop())\n",
      "        else:\n",
      "            res.append(rgt.pop())\n",
      "    res.reverse()\n",
      "    return (lft or rgt) + res"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random\n",
      "lst = list(range(10))\n",
      "seq = random.sample(lst, 10)\n",
      "print seq"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 1, 7, 9, 3, 8, 4, 5, 2, 6]\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mergesort(seq)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Perfect that works also! Note you cannot use numpy arrays with pop I will look up the correct notation. Though you could always use numpyarray.tolist()."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}