sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sort algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge sort is an divide-and-conquer algorithm. The merge-sort tree associated with an execution of merge-sort on a sequence of size n has height floor(logn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def merge(S1, S2, S):\n",
    "    \"\"\"The merge step for array data structure\"\"\"\n",
    "    i = j = 0\n",
    "    while i + j < len(S1) + len(S2):\n",
    "        if (j == len(S2)) or (i < len(S1) and S1[i] <= S2[j]):\n",
    "            S[i+j] = S1[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            S[i+j] = S2[j]\n",
    "            j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge_sort(S):\n",
    "    n = len(S)\n",
    "    if n < 2:\n",
    "        return\n",
    "    \n",
    "    # divide\n",
    "    mid = n//2\n",
    "    S1 = S[0:mid]\n",
    "    S2 = S[mid:n]\n",
    "    # conquer\n",
    "    merge_sort(S1)\n",
    "    merge_sort(S2)\n",
    "    # merge\n",
    "    merge(S1, S2, S)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge(S1, S2, S):\n",
    "    \"\"\"Merge two sorted linked list S1, S2 into linked list S\"\"\"\n",
    "    while not S1.is_empty() and not S2.is_empty():\n",
    "        if S1.first() < S2.first():\n",
    "            S.enqueue(S1.dequeue())\n",
    "        else:\n",
    "            S.enqueue(S2.dequeue()) \n",
    "    while not S1.is_empty():\n",
    "        S.enqueue(S1.dequeue())\n",
    "    while not S2.is_empty():\n",
    "        S.enqueue(S2.dequeue())\n",
    "        \n",
    "\n",
    "def merge_sort(S):\n",
    "    n = len(S)\n",
    "    if n < 2:\n",
    "        return \n",
    "    \n",
    "    S1 = LinkedQueue()\n",
    "    S2 = LinkedQueue()\n",
    "    \n",
    "    while len(S1) < n//2:\n",
    "        S1.enqueue(S.dequeue())\n",
    "    while not S.is_empty():\n",
    "        S2.enqueue(S.dequeue())\n",
    "        \n",
    "    merge_sort(S1)\n",
    "    merge_sort(S2)\n",
    "    merge(S1, S2, S)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The running time of the Merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge algorithm:\n",
    "    Let n1 and n2 be the elements of S1 and S2.  It is clear that the operation performed inside each pass of the while loop take O(1) time. The key observation is that during each iteration of the loop, one element is copy from either S1 or S2 to S. Therefore, the number of iterations of the loop is n1 + n2. Therefoce, the running time of merge algorithm is O(n1+n2).\n",
    "    \n",
    "Merge-sort algorithm:\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}