{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "653a84e1-2b27-4cdb-842f-b879adf6b762",
   "metadata": {},
   "source": [
    "# Insertion sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "454e2d81-759b-4ab6-a6d1-fedd9b7495e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val ins : int * int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec ins (x,l) : int list =\n",
    "  match l with\n",
    "  | [] -> [x]\n",
    "  | y::ys -> if x <= y then x :: y :: ys\n",
    "             else y :: (ins (x, ys))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "6a1fded8-6cae-4b78-afbc-c2ebaa2adb71",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val insort : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec insort = function\n",
    "    | [] -> []\n",
    "    | x::xs -> ins (x,(insort xs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "ad1eb82f-ade2-4275-851d-7ed291b135e0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ins is already traced (under the name ins).\n"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "insort is now traced.\n"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace ins\n",
    "#trace insort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "b9ee048e-e76a-4756-8a01-29cba3a7b8b1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ins <-- (4, [1; 2; 3; 5; 7])\n",
       "ins <-- (4, [2; 3; 5; 7])\n",
       "ins <-- (4, [3; 5; 7])\n",
       "ins <-- (4, [5; 7])\n",
       "ins --> [4; 5; 7]\n",
       "ins --> [3; 4; 5; 7]\n",
       "ins --> [2; 3; 4; 5; 7]\n",
       "ins --> [1; 2; 3; 4; 5; 7]\n",
       "- : int list = [1; 2; 3; 4; 5; 7]\n"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ins (4,[1;2;3;5;7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "3bda731f-85ca-47fd-8fed-dd98a3f8b433",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "insort <-- [2; 1; 5; 3; 6; 4]\n",
       "insort <-- [1; 5; 3; 6; 4]\n",
       "insort <-- [5; 3; 6; 4]\n",
       "insort <-- [3; 6; 4]\n",
       "insort <-- [6; 4]\n",
       "insort <-- [4]\n",
       "insort <-- []\n",
       "insort --> []\n",
       "ins <-- (4, [])\n",
       "ins --> [4]\n",
       "insort --> [4]\n",
       "ins <-- (6, [4])\n",
       "ins <-- (6, [])\n",
       "ins --> [6]\n",
       "ins --> [4; 6]\n",
       "insort --> [4; 6]\n",
       "ins <-- (3, [4; 6])\n",
       "ins --> [3; 4; 6]\n",
       "insort --> [3; 4; 6]\n",
       "ins <-- (5, [3; 4; 6])\n",
       "ins <-- (5, [4; 6])\n",
       "ins <-- (5, [6])\n",
       "ins --> [5; 6]\n",
       "ins --> [4; 5; 6]\n",
       "ins --> [3; 4; 5; 6]\n",
       "insort --> [3; 4; 5; 6]\n",
       "ins <-- (1, [3; 4; 5; 6])\n",
       "ins --> [1; 3; 4; 5; 6]\n",
       "insort --> [1; 3; 4; 5; 6]\n",
       "ins <-- (2, [1; 3; 4; 5; 6])\n",
       "ins <-- (2, [3; 4; 5; 6])\n",
       "ins --> [2; 3; 4; 5; 6]\n",
       "ins --> [1; 2; 3; 4; 5; 6]\n",
       "insort --> [1; 2; 3; 4; 5; 6]\n",
       "- : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insort [2;1;5;3;6;4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "9729cb42-2de3-41f7-bb8c-fdb267b1bbec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "insort <-- [1; 2; 3; 4; 5; 6]\n",
       "insort <-- [2; 3; 4; 5; 6]\n",
       "insort <-- [3; 4; 5; 6]\n",
       "insort <-- [4; 5; 6]\n",
       "insort <-- [5; 6]\n",
       "insort <-- [6]\n",
       "insort <-- []\n",
       "insort --> []\n",
       "ins <-- (6, [])\n",
       "ins --> [6]\n",
       "insort --> [6]\n",
       "ins <-- (5, [6])\n",
       "ins --> [5; 6]\n",
       "insort --> [5; 6]\n",
       "ins <-- (4, [5; 6])\n",
       "ins --> [4; 5; 6]\n",
       "insort --> [4; 5; 6]\n",
       "ins <-- (3, [4; 5; 6])\n",
       "ins --> [3; 4; 5; 6]\n",
       "insort --> [3; 4; 5; 6]\n",
       "ins <-- (2, [3; 4; 5; 6])\n",
       "ins --> [2; 3; 4; 5; 6]\n",
       "insort --> [2; 3; 4; 5; 6]\n",
       "ins <-- (1, [2; 3; 4; 5; 6])\n",
       "ins --> [1; 2; 3; 4; 5; 6]\n",
       "insort --> [1; 2; 3; 4; 5; 6]\n",
       "- : int list = [1; 2; 3; 4; 5; 6]\n"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insort [1;2;3;4;5;6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "426af0ee-42e5-4531-8950-7e70f7ac0646",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "insort <-- [8; 7; 6; 5; 4; 3; 2; 1]\n",
       "insort <-- [7; 6; 5; 4; 3; 2; 1]\n",
       "insort <-- [6; 5; 4; 3; 2; 1]\n",
       "insort <-- [5; 4; 3; 2; 1]\n",
       "insort <-- [4; 3; 2; 1]\n",
       "insort <-- [3; 2; 1]\n",
       "insort <-- [2; 1]\n",
       "insort <-- [1]\n",
       "insort <-- []\n",
       "insort --> []\n",
       "ins <-- (1, [])\n",
       "ins --> [1]\n",
       "insort --> [1]\n",
       "ins <-- (2, [1])\n",
       "ins <-- (2, [])\n",
       "ins --> [2]\n",
       "ins --> [1; 2]\n",
       "insort --> [1; 2]\n",
       "ins <-- (3, [1; 2])\n",
       "ins <-- (3, [2])\n",
       "ins <-- (3, [])\n",
       "ins --> [3]\n",
       "ins --> [2; 3]\n",
       "ins --> [1; 2; 3]\n",
       "insort --> [1; 2; 3]\n",
       "ins <-- (4, [1; 2; 3])\n",
       "ins <-- (4, [2; 3])\n",
       "ins <-- (4, [3])\n",
       "ins <-- (4, [])\n",
       "ins --> [4]\n",
       "ins --> [3; 4]\n",
       "ins --> [2; 3; 4]\n",
       "ins --> [1; 2; 3; 4]\n",
       "insort --> [1; 2; 3; 4]\n",
       "ins <-- (5, [1; 2; 3; 4])\n",
       "ins <-- (5, [2; 3; 4])\n",
       "ins <-- (5, [3; 4])\n",
       "ins <-- (5, [4])\n",
       "ins <-- (5, [])\n",
       "ins --> [5]\n",
       "ins --> [4; 5]\n",
       "ins --> [3; 4; 5]\n",
       "ins --> [2; 3; 4; 5]\n",
       "ins --> [1; 2; 3; 4; 5]\n",
       "insort --> [1; 2; 3; 4; 5]\n",
       "ins <-- (6, [1; 2; 3; 4; 5])\n",
       "ins <-- (6, [2; 3; 4; 5])\n",
       "ins <-- (6, [3; 4; 5])\n",
       "ins <-- (6, [4; 5])\n",
       "ins <-- (6, [5])\n",
       "ins <-- (6, [])\n",
       "ins --> [6]\n",
       "ins --> [5; 6]\n",
       "ins --> [4; 5; 6]\n",
       "ins --> [3; 4; 5; 6]\n",
       "ins --> [2; 3; 4; 5; 6]\n",
       "ins --> [1; 2; 3; 4; 5; 6]\n",
       "insort --> [1; 2; 3; 4; 5; 6]\n",
       "ins <-- (7, [1; 2; 3; 4; 5; 6])\n",
       "ins <-- (7, [2; 3; 4; 5; 6])\n",
       "ins <-- (7, [3; 4; 5; 6])\n",
       "ins <-- (7, [4; 5; 6])\n",
       "ins <-- (7, [5; 6])\n",
       "ins <-- (7, [6])\n",
       "ins <-- (7, [])\n",
       "ins --> [7]\n",
       "ins --> [6; 7]\n",
       "ins --> [5; 6; 7]\n",
       "ins --> [4; 5; 6; 7]\n",
       "ins --> [3; 4; 5; 6; 7]\n",
       "ins --> [2; 3; 4; 5; 6; 7]\n",
       "ins --> [1; 2; 3; 4; 5; 6; 7]\n",
       "insort --> [1; 2; 3; 4; 5; 6; 7]\n",
       "ins <-- (8, [1; 2; 3; 4; 5; 6; 7])\n",
       "ins <-- (8, [2; 3; 4; 5; 6; 7])\n",
       "ins <-- (8, [3; 4; 5; 6; 7])\n",
       "ins <-- (8, [4; 5; 6; 7])\n",
       "ins <-- (8, [5; 6; 7])\n",
       "ins <-- (8, [6; 7])\n",
       "ins <-- (8, [7])\n",
       "ins <-- (8, [])\n",
       "ins --> [8]\n",
       "ins --> [7; 8]\n",
       "ins --> [6; 7; 8]\n",
       "ins --> [5; 6; 7; 8]\n",
       "ins --> [4; 5; 6; 7; 8]\n",
       "ins --> [3; 4; 5; 6; 7; 8]\n",
       "ins --> [2; 3; 4; 5; 6; 7; 8]\n",
       "ins --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "insort --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "- : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insort [8;7;6;5;4;3;2;1]"
   ]
  }
 ],
 "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
}