{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to *Merge $k$ sorted lists* (in Python 3)\n",
    "\n",
    "The question comes from [this nice blog on programming](https://tianrunhe.wordpress.com/2012/11/04/merge-k-sorted-lists/).\n",
    "I will solve it without giving much details, and test it quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge_two(list1, list2):\n",
    "    if len(list1) == 0:\n",
    "        return list2[:]\n",
    "    elif len(list2) == 0:\n",
    "        return list1[:]\n",
    "    else:\n",
    "        if list1[0] < list2[0]:\n",
    "            return [list1[0]] + merge_two(list1[1:], list2)\n",
    "        else:\n",
    "            return [list2[0]] + merge_two(list1, list2[1:])\n",
    "    \n",
    "\n",
    "def merge(*lists):\n",
    "    head = []\n",
    "    for list_i in lists:\n",
    "        head = merge_two(head, list_i)\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def random_sorted_list(size):\n",
    "    return sorted([random.randint(0, 100) for _ in range(size)])\n",
    "\n",
    "\n",
    "def issorted(alist):\n",
    "    return alist == sorted(alist) \n",
    "\n",
    "\n",
    "for size in [10, 20, 30]:\n",
    "    for k in range(2, 20):\n",
    "        lists = [random_sorted_list(size) for _ in range(k)]\n",
    "        merged_list = merge(*lists)\n",
    "        assert issorted(merged_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexity\n",
    "One can prove that the algorithm we proposed is:\n",
    "\n",
    "- correctly merging $k$ sorted list into a sorted list containing the values from all the list,\n",
    "- and does so with an extra memory of at most $\\mathcal{O}(k n)$ if all the lists have size at most $n$,\n",
    "- and does so with a time complexity of at most $\\mathcal{O}(k n)$ if all the lists have size at most $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Conclusion\n",
    "*Et voilà.*"
   ]
  }
 ],
 "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.5.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "86px",
    "width": "251px"
   },
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}