Mergesort_Notes.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.8.6"
    },
    "colab": {
      "provenance": [],
      "collapsed_sections": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mhlOzjPdyJew"
      },
      "source": [
        "These notes are meant to augment the presentation of the merge-sort algorithm presented in the lecture. \n",
        "\n",
        "The main idea behind merge sort of a list of size `n` is to \n",
        "  1. Split the list into two \"sublists\" of size `n/2`\n",
        "  2. Sort the sublists\n",
        "  3. Merge the result.\n",
        "\n",
        "### Merging Sorted Lists\n",
        "\n",
        "We will first focus on the merge procedure that given two lists\n",
        "`lst1` and `lst2` which are sorted in ascending order, returns \n",
        "a list that contains all the elements in `lst1` and `lst2` and is\n",
        "in sorted order. \n",
        "\n",
        "The main idea behind merge is to maintain two indices `i1` and `i2`, \n",
        "where `i1` is an index for `lst1` and `i2` is an index for `lst2`.\n",
        "\n",
        "  - If `lst1[i1] <= lst2[i2]` then we take the element `lst1[i1]` and  append it at the end of our output list. We then advance the index `i1`.\n",
        "  - Alternatively, `lst1[i1] > lst2[i2]`, then we take `lst2[i2]` and append it to the end of our output list. We then advance the index `i2`.\n",
        "\n",
        "If in the process above, we run over the end of the list, we simply copy the remaining elements of the other list."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nhixhVspyJe3"
      },
      "source": [
        "def mergeLists(lst1, lst2):\n",
        "    n1 = len(lst1)\n",
        "    n2 = len(lst2)\n",
        "    if n1 == 0: # lst1 is empty\n",
        "        return list(lst2)\n",
        "    elif n2 == 0:\n",
        "        return list(lst1)\n",
        "    else:\n",
        "        output_lst = [] # This is the list we will return\n",
        "        i1 = 0\n",
        "        i2 = 0\n",
        "        while (i1 < n1 or i2 < n2):\n",
        "            if i1 < n1 and i2 < n2: # We are processing both lists\n",
        "                if (lst1[i1] <= lst2[i2]): # lst[i1] is the smaller elt\n",
        "                    output_lst.append(lst1[i1]) # append to end of output list\n",
        "                    i1 = i1 + 1 # advance index i1\n",
        "                else:\n",
        "                    output_lst.append(lst2[i2]) # append to end of output list\n",
        "                    i2 = i2 + 1 # advance index i2\n",
        "            elif i1 < n1: # We have run past the end of lst2\n",
        "                output_lst.append(lst1[i1]) # append lst1 to end of output list\n",
        "                i1 = i1 + 1\n",
        "            else:  # We have run past the end of lst1\n",
        "                output_lst.append(lst2[i2]) # append lst2 to end of output list\n",
        "                i2 = i2 + 1\n",
        "        return output_lst"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tSrWSrjcyJe4",
        "outputId": "16c7f4fa-0c42-437a-b775-61b895db6f45"
      },
      "source": [
        "# TEST CASES\n",
        "lst1 = mergeLists([0, 2, 3, 7, 10], [1, 4, 5, 6, 7, 8, 9, 10, 11, 12])\n",
        "print('lst1: %s' % str(lst1))\n",
        "assert lst1 == [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12]\n",
        "\n",
        "lst2 = mergeLists([0,2],[1,3,6])\n",
        "print('lst2: %s' % str(lst2))\n",
        "assert lst2 == [0, 1, 2, 3, 6]\n",
        "\n",
        "lst3 = mergeLists([0], [0])\n",
        "\n",
        "print('lst3: %s' % str(lst3))\n",
        "assert lst3 == [0, 0]\n",
        "\n",
        "lst4 = mergeLists([], [0, 1, 5])\n",
        "print('lst4: %s' % str(lst4))\n",
        "assert lst4 == [0, 1, 5]\n",
        "\n",
        "lst5 = mergeLists([0, 1, 5], [])\n",
        "print('lst5: %s' % str(lst5))\n",
        "assert lst5 == [0, 1, 5]\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "lst1: [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12]\n",
            "lst2: [0, 1, 2, 3, 6]\n",
            "lst3: [0, 0]\n",
            "lst4: [0, 1, 5]\n",
            "lst5: [0, 1, 5]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-fyJ1NLiyJe6"
      },
      "source": [
        "## Correctness of Merge Algorithm\n",
        "\n",
        "The correctness of merge algorithm is given by the following \"loop invariant\" that holds whenever we are running the main loop of the algorithm.\n",
        "\n",
        "\n",
        "```python\n",
        "while (i1 < n1 or i2 < n2): ## WHILE LOOP \n",
        "    if i1 < n1 and i2 < n2: \n",
        "        if (lst1[i1] <= lst2[i2]): \n",
        "            output_lst.append(lst1[i1]) \n",
        "            i1 = i1 + 1 \n",
        "        else:\n",
        "            output_lst.append(lst2[i2]) \n",
        "            i2 = i2 + 1 \n",
        "        elif i1 < n1: \n",
        "            output_lst.append(lst1[i1]) \n",
        "            i1 = i1 + 1\n",
        "        else: \n",
        "            output_lst.append(lst2[i2]) \n",
        "            i2 = i2 + 1\n",
        "```\n",
        "\n",
        "\n",
        "**Loop Invariant** The loop invariant is the condition that is established during each iteration of the WHILE LOOP whenever the control reaches the loop head. For this algorithm the key loop invariants are\n",
        "  - `0 <= i1 <= n1` and `0 <= i2 <= n2`\n",
        "  - `output_lst` is the merge of the _sublists_ `lst1[0:i1]` and `lst2[0:i2]`.\n",
        "    - Note that in python `lst[0:j]` refers to all elements from 0 to j-1. In particular, this is the empty sublist of `j == 0`.\n",
        "  - If `output_lst` is non-empty and `i1 < n1`, then the last element of `output_lst` is less than or equal to `lst1[i1]` \n",
        "  - If `output_lst` is non-empty and `i2 < n2` then the last element of `output_lst` is less than or equal to `lst2[i2]`.\n",
        "  - `output_lst` is sorted in ascending order.\n",
        "\n",
        "**TODO # 1** Convince yourself that the loop invariants all hold at the very beginning when we initialize `i1, i2` and `output_lst` as follows:\n",
        "  - `i1 = i2 = 0`\n",
        "  - `output_lst = []`\n",
        "  \n",
        "  \n",
        "**TODO # 2** Convinuce yourself that if at the beginning of any loop iteration the invariant conditions hold, then it must hold after one further iteration. \n",
        "  - This is somewhat onerous but is a very useful exercise.\n",
        "\n",
        "\n",
        "Note that the while loop exits only when `i1 = n1` and `i2 = n2`. Therefore, the loop invariants imply that when the loop is done:\n",
        "  - `output_lst` is the merge of the lists `lst1` and `lst2`.\n",
        "  - `output_lst` is sorted in ascending order.\n",
        "  \n",
        "**Termination** \n",
        "\n",
        "Note that `i1` or `i2` must increase in each loop iteration and `i1` cannot exceed `n1` and `i2` cannot exceed `n2`. Thus, the loop cannot iterate forever.\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zTfN_5Rbyv_d"
      },
      "source": [
        "## Mergesort Algorithm\n",
        "\n",
        "We are now ready to code up the full mergesort algorithm. We will reimplement the merge algorithm as well."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-5Kgn7T2yJe6"
      },
      "source": [
        "# helper function to swap the elements at two positions in the list\n",
        "def swap(lst, i, j):\n",
        "    n = len(lst)\n",
        "    assert( i >= 0 and i < n)\n",
        "    assert( j >= 0 and j < n)\n",
        "    # We can use a simultaneous assignmment to swap\n",
        "    (lst[i], lst[j]) = (lst[j], lst[i])\n",
        "    return \n",
        "\n",
        "# this function copies the result of the merge back into the original list\n",
        "# Function: copy_back\n",
        "# output_lst is the list that contains right - left + 1 elements.\n",
        "# lst is the list we need to copy into\n",
        "# left and right are indices into list.\n",
        "# TODO: copy elements from output_lst into lst[left:right+1]\n",
        "# Note that python range left:right+1 includes indices from left,..., right.\n",
        "\n",
        "def copy_back(output_lst, lst, left, right):\n",
        "    # Ensure that the output has the right length for us to copy back\n",
        "    assert(len(output_lst) == right - left + 1)\n",
        "    for i in range(left, right+1):\n",
        "        lst[i] = output_lst[i - left]\n",
        "    return \n",
        "\n",
        "#Function: mergeHelper\n",
        "# merge elements from lst[left:mid+1]  and lst[mid+1:right+1]\n",
        "# create a temporary output list to hold the merged result and\n",
        "# copy that back using the copy_back function.\n",
        "# This was lst is modified in place. \n",
        "def mergeHelper(lst, left, mid, right):\n",
        "    # Perform a merge on sublists lst[left:mid+1] and lst[mid+1:right+1]\n",
        "    # This is the same algorithm as merge above but we will need to copy\n",
        "    # things back to the original list.\n",
        "    if left > mid or mid > right:  # one of the two sublists is empty\n",
        "        return\n",
        "    i1 = left\n",
        "    i2 = mid + 1\n",
        "    output_lst = []\n",
        "    while (i1 <= mid or i2 <= right):\n",
        "        if (i1 <= mid and i2 <= right):\n",
        "            if lst[i1] <= lst[i2]:\n",
        "                output_lst.append(lst[i1])\n",
        "                i1 = i1 + 1\n",
        "            else:\n",
        "                output_lst.append(lst[i2])\n",
        "                i2 = i2 + 1\n",
        "        elif i1 <= mid:\n",
        "            output_lst.append(lst[i1])\n",
        "            i1 = i1 + 1\n",
        "        else:\n",
        "            output_lst.append(lst[i2])\n",
        "            i2 = i2 + 1\n",
        "    copy_back(output_lst, lst, left, right)\n",
        "    return \n",
        "# Function: mergeSortHelper\n",
        "# recursive implementation of mergesort.\n",
        "def mergesortHelper(lst, left, right):\n",
        "    if (left == right): # Region to sort is just a singleton\n",
        "        return \n",
        "    elif (left + 1 == right): # region to sort has two elements\n",
        "        if (lst[left] > lst[right]): # compare \n",
        "            swap(lst, left, right)   # and swap if needed\n",
        "    else: \n",
        "        mid = (left + right ) // 2  # compute mid point. \n",
        "        # Note that // is integer division in python3.\n",
        "        mergesortHelper(lst, left, mid) # Sort left half recursively\n",
        "        mergesortHelper(lst, mid + 1 , right) # Sort right half recursively\n",
        "        mergeHelper(lst, left, mid, right) # merge them together.\n",
        "        \n",
        "# Function mergesort\n",
        "#   Sort the list in place and modify it so that \n",
        "#   lst is sorted when the function returns.\n",
        "def mergesort(lst):\n",
        "    if len(lst) <= 1:\n",
        "        return # nothing to do\n",
        "    else:\n",
        "        mergesortHelper(lst, 0, len(lst)-1)\n",
        "        "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3nyx9tsKyJe7",
        "outputId": "ca8f7ef8-ae0e-4ec5-be4b-740d787331ab"
      },
      "source": [
        "# Let us run a few test cases \n",
        "\n",
        "lst = [0, 5, 6, 2, 19, -1, 2, 3, 0, 4, 5, 8]\n",
        "mergesort(lst)\n",
        "print(lst)\n",
        "\n",
        "lst1 = [0, 1, 2, 6, 18, 19, -20, -45, -23, 25, 56, 19, 81, 123, 122]\n",
        "mergesort(lst1)\n",
        "print(lst1)\n",
        "\n",
        "lst2 = [4,3,2,1]\n",
        "mergesort(lst2)\n",
        "print(lst2)\n",
        "\n",
        "lst4 = [1]\n",
        "mergesort(lst4)\n",
        "print(lst4)\n",
        "\n",
        "lst5 = []\n",
        "mergesort(lst5)\n",
        "print(lst5)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[-1, 0, 0, 2, 2, 3, 4, 5, 5, 6, 8, 19]\n",
            "[-45, -23, -20, 0, 1, 2, 6, 18, 19, 19, 25, 56, 81, 122, 123]\n",
            "[1, 2, 3, 4]\n",
            "[1]\n",
            "[]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qlJgEfD5yJe8"
      },
      "source": [
        "### Correctness of Mergesort\n",
        "\n",
        "```python\n",
        "def mergesortHelper(lst, left, right):\n",
        "    if (left == right): # Region to sort is just a singleton\n",
        "        return \n",
        "    elif (left + 1 == right): # region to sort has two elements\n",
        "        if (lst[left] > lst[right]): # compare \n",
        "            swap(lst, left, right)   # and swap if needed\n",
        "    else: \n",
        "        mid = (left + right ) // 2  # compute mid point\n",
        "        mergesortHelper(lst, left, mid) # Sort left half\n",
        "        mergesortHelper(lst, mid + 1 , right) # Sort right half\n",
        "        mergeHelper(lst, left, mid, right) # merge them together.\n",
        "```\n",
        "\n",
        "We establish the following properties whenever we call the function `mergesortHelper` with arguments `lst, left, right`.\n",
        "  - `0 <= left <= right < len(lst)`.\n",
        " \n",
        "We have to assume that `mergeHelper` correctly merges the two sorted sublists `lst[left:mid+1]` and `lst[mid+1:right+1]` resulting in a sorted and merged sublist `lst[left:right+1]`. \n",
        " \n",
        "We can then prove by induction that when `mergesortHelper` exits the sublist `lst[left:right+1]` is sorted. Recall the sublist notation from above.\n",
        "   * Base Cases : `left == right`. The sublist is trivially sorted.\n",
        "      * `left +1 == right`: The sublist has two elements and we note by inspecting the code that by comparing `lst[left], lst[right]` and swapping them, the algorithm ensures that `lst[left:right+1]` is sorted.\n",
        "   * Induction: Let `k = right - left + 1` be the size of the region we are asked to sort. Assume that `mergesortHelper` correctly sorts whenever the sorting region has size strictly less than k. Therefore, after we have the calls to sort the left half and right half, we ensure that the two sublists `lst[left:mid+1]` and `lst[mid+1:right+1]` are themselves sorted. Finally, we appeal to the correctness of `mergeHelper` method and note that the entire sublist `lst[left:right+1]` ends up sorted when we exit the `mergesort` procedure."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xsqTEogayJe8"
      },
      "source": [
        "### Running Time Complexity of Mergesort\n",
        "\n",
        "This analysis was provided as part of the lecture. We noted that\n",
        "the running time complexity of mergesort was $\\Theta(n \\log(n))$ for an input list of size $n$."
      ]
    }
  ]
}