merge_sort.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "id": "f8c678c7-180b-418b-8f39-08b9f8a5aa32",
   "metadata": {},
   "source": [
    "---\n",
    "title: Visualising sorting of numbers in merge sort\n",
    "description: using recursion\n",
    "show-code: False\n",
    "params: \n",
    "    texts:\n",
    "        input: text\n",
    "        label: Enter numbers to sort separated by comma\n",
    "        value: 5,2,19,3,100,6\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "77d54c3d-3582-4398-be8c-346baba005e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import mercury as mr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "207ffa0d-f9fa-4753-966d-40ee128dedea",
   "metadata": {},
   "outputs": [],
   "source": [
    "#app = mr.App(title=\"Visualising sorting of numbers using recursion in merge sort\", description=\"using merge sort\")\n",
    "texts = '5,2,19,3,100,6'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "afd50440-2a60-4e9e-a2dc-783a996ddef7",
   "metadata": {},
   "outputs": [],
   "source": [
    "#texts = [mr.Text(label=f\"Enter numbers to sort separated by comma\", value=f\"5,2,19,3,6,10\", url_key=f\"w-{0}\")]\n",
    "#texts = []\n",
    "#for i in range(5):\n",
    "#    texts += [mr.Text(label=f\"Widget {i}\", value=f\"{i}\", url_key=f\"w-{i}\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "81f4c406-8b10-423b-947a-ab5c09cd21fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "texts = (texts).split(',')\n",
    "texts = [int(t) for t in texts]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "cb2bf025-f51b-4d1f-a2df-6848d9088e18",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sorting  [5, 2, 19, 3, 100, 6]\n",
      "  /\n",
      " [5, 2, 19]\n",
      "   /\n",
      " [5]\n",
      "         \\\n",
      "        [2, 19]\n",
      "     /\n",
      "   [2]\n",
      "           \\\n",
      "          [19]\n",
      "merging [2] and [19]\n",
      "merging [5] and [2, 19]\n",
      "            \\\n",
      "           [3, 100, 6]\n",
      "        /\n",
      "      [3]\n",
      "              \\\n",
      "             [100, 6]\n",
      "          /\n",
      "        [100]\n",
      "                \\\n",
      "               [6]\n",
      "merging [100] and [6]\n",
      "merging [3] and [6, 100]\n",
      "merging [2, 5, 19] and [3, 6, 100]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 6, 19, 100]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# implement merge sort algo for sorting a list x using recursion\n",
    "\n",
    "# merge 2 lists and sort the values by taking min value for first element in both list\n",
    "# and remove that element from the list which has min value\n",
    "# because both lists already sorted, doing this way wil give combined 1 list which is sorted\n",
    "def merge(left, right, x):\n",
    "  print('merging', left, 'and', right)\n",
    "  i = j = k = 0\n",
    "  while i < len(left) and j < len(right):\n",
    "    if left[i] < right[j]:\n",
    "      x[k] = left[i]\n",
    "      i = i + 1\n",
    "    else:\n",
    "      x[k] = right[j]\n",
    "      j = j + 1\n",
    "    k = k + 1\n",
    "\n",
    "  while i < len(left):\n",
    "    x[k] = left[i]\n",
    "    i = i + 1\n",
    "    k = k + 1\n",
    "\n",
    "  while j < len(right):\n",
    "    x[k] = right[j]\n",
    "    j = j + 1\n",
    "    k = k + 1\n",
    "\n",
    "  return x\n",
    "\n",
    "# actual function that sorts list x that calls itself using recursion\n",
    "def sortarray(x):\n",
    "\n",
    "  # counter increment by 1 everytime function sortarray is called\n",
    "  # used for increasing spacing during printing of \\,/ and list\n",
    "  sortarray.counter +=1\n",
    "\n",
    "  if len(x) > 1:\n",
    "    l = int(len(x)/2)\n",
    "    left = x[:l]\n",
    "    right = x[l:]\n",
    "\n",
    "    # a / is printed when list is split to left half\n",
    "    print(' '* (sortarray.counter), '/')\n",
    "    print(' '* (sortarray.counter - 2), left)\n",
    "    sortarray(left)\n",
    "\n",
    "    # a / is printed when list is split to right half\n",
    "    print(' '* (sortarray.counter + 5), '\\\\')\n",
    "    print(' '* (sortarray.counter + 5 - 1), right)\n",
    "    sortarray(right)\n",
    "\n",
    "    merge(left, right, x)\n",
    "\n",
    "  return x\n",
    "\n",
    "sortarray.counter = 0\n",
    "print('sorting ', texts)\n",
    "sortarray(texts)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}