4 Algorithmen Grundlagen/7-Sorting and Searching/8-Implementation of Merge Sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of Merge Sort\n",
    "\n",
    "Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources for Review\n",
    "\n",
    "Check out the resources below for a review of Merge sort!\n",
    "\n",
    "* [Wikipedia](https://en.wikipedia.org/wiki/Merge_sort)\n",
    "* [Visual Algo](http://visualgo.net/sorting.html)\n",
    "* [Sorting Algorithms Animcation with Pseudocode](http://www.sorting-algorithms.com/merge-sort)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge_sort(arr):\n",
    "    \n",
    "    if len(arr)>1:\n",
    "        mid = len(arr)/2\n",
    "        lefthalf = arr[:mid]\n",
    "        righthalf = arr[mid:]\n",
    "\n",
    "        merge_sort(lefthalf)\n",
    "        merge_sort(righthalf)\n",
    "\n",
    "        i=0\n",
    "        j=0\n",
    "        k=0\n",
    "        while i < len(lefthalf) and j < len(righthalf):\n",
    "            if lefthalf[i] < righthalf[j]:\n",
    "                arr[k]=lefthalf[i]\n",
    "                i=i+1\n",
    "            else:\n",
    "                arr[k]=righthalf[j]\n",
    "                j=j+1\n",
    "            k=k+1\n",
    "\n",
    "        while i < len(lefthalf):\n",
    "            arr[k]=lefthalf[i]\n",
    "            i=i+1\n",
    "            k=k+1\n",
    "\n",
    "        while j < len(righthalf):\n",
    "            arr[k]=righthalf[j]\n",
    "            j=j+1\n",
    "            k=k+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 6, 7, 8, 11, 23]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [11,2,5,4,7,6,8,1,23]\n",
    "merge_sort(arr)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}