{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "731cea62-4d47-4a21-8c65-58150bce9353",
   "metadata": {},
   "source": [
    "# Mergesort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ff21354a-58e5-4985-8863-220b11494716",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val take : 'a list * int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val drop : 'a list * int -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val merge : int list * int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val tmergesort : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec take = function\n",
    "  | ([], _) -> []\n",
    "  | (x::xs, i) ->\n",
    "     if i>0 then\n",
    "        x :: take (xs, i - 1)\n",
    "     else\n",
    "        []\n",
    "let rec drop = function\n",
    "  | ([], _) -> []\n",
    "  | (x::xs, i) ->\n",
    "     if i>0 then\n",
    "       drop (xs, i-1)\n",
    "     else\n",
    "       x::xs\n",
    "let rec merge : int list * int list -> int list = function\n",
    "  | [], ys -> ys\n",
    "  | xs, [] -> xs\n",
    "  | x::xs, y::ys ->\n",
    "      if x <= y then\n",
    "        x :: merge (xs, y::ys)\n",
    "      else\n",
    "        y :: merge (x::xs, ys)\n",
    "let rec tmergesort = function\n",
    "  | [] -> []\n",
    "  | [x] -> [x]\n",
    "  | xs ->\n",
    "      let k = List.length xs / 2 in\n",
    "      let l = tmergesort (take (xs, k)) in\n",
    "      let r = tmergesort (drop (xs, k)) in\n",
    "      merge (l, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6405dc9f-861a-49cb-83a2-e1c7c5185f48",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "merge is now traced.\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "tmergesort is now traced.\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace merge\n",
    "#trace tmergesort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c6736f2a-c171-4ae7-93bf-855b88f27222",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "merge <-- ([1; 3; 5], [2; 4; 6])\n",
       "merge <-- ([3; 5], [2; 4; 6])\n",
       "merge <-- ([3; 5], [4; 6])\n",
       "merge <-- ([5], [4; 6])\n",
       "merge <-- ([5], [6])\n",
       "merge <-- ([], [6])\n",
       "merge --> [6]\n",
       "merge --> [5; 6]\n",
       "merge --> [4; 5; 6]\n",
       "merge --> [3; 4; 5; 6]\n",
       "merge --> [2; 3; 4; 5; 6]\n",
       "merge --> [1; 2; 3; 4; 5; 6]\n",
       "- : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge ([1;3;5],[2;4;6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "89b4da92-a25d-4490-86b2-1a58b03997aa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tmergesort <-- [4; 5; 2; 6; 3; 7; 1; 8]\n",
       "tmergesort <-- [4; 5; 2; 6]\n",
       "tmergesort <-- [4; 5]\n",
       "tmergesort <-- [4]\n",
       "tmergesort --> [4]\n",
       "tmergesort <-- [5]\n",
       "tmergesort --> [5]\n",
       "merge <-- ([4], [5])\n",
       "merge <-- ([], [5])\n",
       "merge --> [5]\n",
       "merge --> [4; 5]\n",
       "tmergesort --> [4; 5]\n",
       "tmergesort <-- [2; 6]\n",
       "tmergesort <-- [2]\n",
       "tmergesort --> [2]\n",
       "tmergesort <-- [6]\n",
       "tmergesort --> [6]\n",
       "merge <-- ([2], [6])\n",
       "merge <-- ([], [6])\n",
       "merge --> [6]\n",
       "merge --> [2; 6]\n",
       "tmergesort --> [2; 6]\n",
       "merge <-- ([4; 5], [2; 6])\n",
       "merge <-- ([4; 5], [6])\n",
       "merge <-- ([5], [6])\n",
       "merge <-- ([], [6])\n",
       "merge --> [6]\n",
       "merge --> [5; 6]\n",
       "merge --> [4; 5; 6]\n",
       "merge --> [2; 4; 5; 6]\n",
       "tmergesort --> [2; 4; 5; 6]\n",
       "tmergesort <-- [3; 7; 1; 8]\n",
       "tmergesort <-- [3; 7]\n",
       "tmergesort <-- [3]\n",
       "tmergesort --> [3]\n",
       "tmergesort <-- [7]\n",
       "tmergesort --> [7]\n",
       "merge <-- ([3], [7])\n",
       "merge <-- ([], [7])\n",
       "merge --> [7]\n",
       "merge --> [3; 7]\n",
       "tmergesort --> [3; 7]\n",
       "tmergesort <-- [1; 8]\n",
       "tmergesort <-- [1]\n",
       "tmergesort --> [1]\n",
       "tmergesort <-- [8]\n",
       "tmergesort --> [8]\n",
       "merge <-- ([1], [8])\n",
       "merge <-- ([], [8])\n",
       "merge --> [8]\n",
       "merge --> [1; 8]\n",
       "tmergesort --> [1; 8]\n",
       "merge <-- ([3; 7], [1; 8])\n",
       "merge <-- ([3; 7], [8])\n",
       "merge <-- ([7], [8])\n",
       "merge <-- ([], [8])\n",
       "merge --> [8]\n",
       "merge --> [7; 8]\n",
       "merge --> [3; 7; 8]\n",
       "merge --> [1; 3; 7; 8]\n",
       "tmergesort --> [1; 3; 7; 8]\n",
       "merge <-- ([2; 4; 5; 6], [1; 3; 7; 8])\n",
       "merge <-- ([2; 4; 5; 6], [3; 7; 8])\n",
       "merge <-- ([4; 5; 6], [3; 7; 8])\n",
       "merge <-- ([4; 5; 6], [7; 8])\n",
       "merge <-- ([5; 6], [7; 8])\n",
       "merge <-- ([6], [7; 8])\n",
       "merge <-- ([], [7; 8])\n",
       "merge --> [7; 8]\n",
       "merge --> [6; 7; 8]\n",
       "merge --> [5; 6; 7; 8]\n",
       "merge --> [4; 5; 6; 7; 8]\n",
       "merge --> [3; 4; 5; 6; 7; 8]\n",
       "merge --> [2; 3; 4; 5; 6; 7; 8]\n",
       "merge --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "tmergesort --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "- : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tmergesort [4;5;2;6;3;7;1;8]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.14",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.14.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}