merge_sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Merge sort implementation\n",
    "# Speed: O(n log n)\n",
    "\n",
    "def mergeSort(input_list):\n",
    "    # as long as there are items in the list, sort\n",
    "    if len(input_list) > 1:\n",
    "\n",
    "        # cut the list into halves (roughly if odd) using floor division\n",
    "        midpoint = len(input_list) // 2\n",
    "        left_list = input_list[:midpoint]\n",
    "        right_list = input_list[midpoint:]\n",
    "\n",
    "        # recursively call the function on each half\n",
    "        mergeSort(left_list)\n",
    "        mergeSort(right_list)\n",
    "\n",
    "        # initialize counters and empty list that will contain sorted values\n",
    "        i = 0\n",
    "        j = 0\n",
    "        k = 0\n",
    "\n",
    "        # step through each list\n",
    "        while i < len(left_list) and j < len(right_list):\n",
    "            # if left is less than, assign it to the position in input_list\n",
    "            if left_list[i] < right_list[j]:\n",
    "                input_list[k] = left_list[i]\n",
    "                i += 1\n",
    "\n",
    "            # otherwise, assign the right instead\n",
    "            else:\n",
    "                input_list[k] = right_list[j]\n",
    "                j += 1\n",
    "\n",
    "            # advance the position of the input_list\n",
    "            k += 1\n",
    "\n",
    "        # handle cases where lists are not the same length and there are remaining items\n",
    "        while i < len(left_list):\n",
    "            input_list[k] = left_list[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "\n",
    "        while j < len(right_list):\n",
    "            input_list[k] = right_list[j]\n",
    "            j += 1\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 3, 5, 7, 44, 77, 89, 9988]\n"
     ]
    }
   ],
   "source": [
    "test_list = [2,7,9988,3,77,3,44,5,1,89]\n",
    "mergeSort(test_list)\n",
    "print(test_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "d6b62a67c3cb82c59c22fc1ee8c926e5c2fdaecb1657b4815a0a3d88bd553adb"
  },
  "kernelspec": {
   "display_name": "Python 3.8.5 ('base')",
   "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"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}