Merge_Sort.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Merge Sort.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNDU+78lvUIlqCBGJFdENgM",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/saima8/DS-and-Algo/blob/main/Merge_Sort.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-CdKUCGxyUJP"
      },
      "source": [
        "**1**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "N_St1SGuxlC-"
      },
      "source": [
        "#interviewbit\n",
        "# merge function take two intervals\n",
        "# one from start to mid\n",
        "# second from mid+1 to end\n",
        "# and merge them in sorted order\n",
        "\n",
        "def merge(arr, start, mid, end):\n",
        "  #create a temp array\n",
        "  temp[] = [0] * (end - start + 1)\n",
        "\n",
        "  #crawlers for both  intervals and for temp\n",
        "  i, j, k = start, mid+1, 0\n",
        "\n",
        "  # traverse both lists and in each iteration add smaller of both elements in temp\n",
        "\n",
        "  while (i <= mid and j <= end):\n",
        "    if(arr[i] <= arr[j]):\n",
        "      temp[k] = arr[i]\n",
        "      k += 1; j += 1\n",
        "    else:\n",
        "      temp[k] = arr[j]\n",
        "      k += 1; i += 1\n",
        "  # add elements left in the first interval\n",
        "  while (i <= mid):\n",
        "    temp[k] = arr[j]\n",
        "    k += 1; i += 1\n",
        "\n",
        "  # add elements left in the second interval\n",
        "  while (j <= end):\n",
        "    temp[k] = arr[j]\n",
        "    k += 1; j += 1\n",
        "  # copy temp to original interval\n",
        "  for i in range (start, end+1):\n",
        "    arr[i] = temp[i - start]\n",
        "\n",
        "def mergeSort(arr, start, end):\n",
        "  if (start < end):\n",
        "    mid = (start + end) / 2\n",
        "    mergeSort(arr, start, mid)\n",
        "    mergeSort(arr, mid+1, end)\n",
        "    merge(arr, start, mid, end)"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fC4XPCGf5roT"
      },
      "source": [
        "**2**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3F5JvdBZ5joO",
        "outputId": "57513cdc-bf03-49e1-ebe5-04250d86e5ef"
      },
      "source": [
        "# Python program for implementation of MergeSort\n",
        "def mergeSort(arr):\n",
        "\tif len(arr) > 1:\n",
        "\n",
        "\t\t# Finding the mid of the array\n",
        "\t\tmid = len(arr)//2\n",
        "\n",
        "\t\t# Dividing the array elements\n",
        "\t\tL = arr[:mid]\n",
        "\n",
        "\t\t# into 2 halves\n",
        "\t\tR = arr[mid:]\n",
        "\n",
        "\t\t# Sorting the first half\n",
        "\t\tmergeSort(L)\n",
        "\n",
        "\t\t# Sorting the second half\n",
        "\t\tmergeSort(R)\n",
        "\n",
        "\t\ti = j = k = 0\n",
        "\n",
        "\t\t# Copy data to temp arrays L[] and R[]\n",
        "\t\twhile i < len(L) and j < len(R):\n",
        "\t\t\tif L[i] < R[j]:\n",
        "\t\t\t\tarr[k] = L[i]\n",
        "\t\t\t\ti += 1\n",
        "\t\t\telse:\n",
        "\t\t\t\tarr[k] = R[j]\n",
        "\t\t\t\tj += 1\n",
        "\t\t\tk += 1\n",
        "\n",
        "\t\t# Checking if any element was left\n",
        "\t\twhile i < len(L):\n",
        "\t\t\tarr[k] = L[i]\n",
        "\t\t\ti += 1\n",
        "\t\t\tk += 1\n",
        "\n",
        "\t\twhile j < len(R):\n",
        "\t\t\tarr[k] = R[j]\n",
        "\t\t\tj += 1\n",
        "\t\t\tk += 1\n",
        "\n",
        "# Code to print the list\n",
        "\n",
        "\n",
        "def printList(arr):\n",
        "\tfor i in range(len(arr)):\n",
        "\t\tprint(arr[i], end=\" \")\n",
        "\tprint()\n",
        "\n",
        "\n",
        "# Driver Code\n",
        "if __name__ == '__main__':\n",
        "\tarr = [12, 11, 13, 5, 6, 7]\n",
        "\tprint(\"Given array is\", end=\"\\n\")\n",
        "\tprintList(arr)\n",
        "\tmergeSort(arr)\n",
        "\tprint(\"Sorted array is: \", end=\"\\n\")\n",
        "\tprintList(arr)\n",
        "\n",
        "# This code is contributed by Mayank Khanna\n"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Given array is\n",
            "12 11 13 5 6 7 \n",
            "Sorted array is: \n",
            "5 6 7 11 12 13 \n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X0S4H4pR5uuW"
      },
      "source": [
        "**3**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PQFincxl5xCh",
        "outputId": "3c45360e-c083-4613-c66e-0cc941145b42"
      },
      "source": [
        "#w3resource\n",
        "\n",
        "def mergeSort(nlist):\n",
        "  print(nlist)\n",
        "  if len(nlist) > 1:\n",
        "    mid = len(nlist) // 2\n",
        "    left = nlist[:mid]\n",
        "    right = nlist[mid:]\n",
        "\n",
        "    mergeSort(left)\n",
        "    mergeSort(right)\n",
        "\n",
        "    i=j=k=0\n",
        "    while i < len(left) and j < len(right):\n",
        "      if left[i] < right[j]:\n",
        "        nlist[k] = left[i]\n",
        "        i += 1\n",
        "      else:\n",
        "        nlist[k] = right[j]\n",
        "        j += 1\n",
        "      k += 1\n",
        "\n",
        "    while i < len(left):\n",
        "      nlist[k] = left[i]\n",
        "      i += 1\n",
        "      k += 1\n",
        "    while j < len(right):\n",
        "      j += 1\n",
        "      k += 1\n",
        "  print(\"merging \", nlist)\n",
        "\n",
        "nlist = [14,46,43,27,57,41,45,21,70]\n",
        "mergeSort(nlist)"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[14, 46, 43, 27, 57, 41, 45, 21, 70]\n",
            "[14, 46, 43, 27]\n",
            "[14, 46]\n",
            "[14]\n",
            "merging  [14]\n",
            "[46]\n",
            "merging  [46]\n",
            "merging  [14, 46]\n",
            "[43, 27]\n",
            "[43]\n",
            "merging  [43]\n",
            "[27]\n",
            "merging  [27]\n",
            "merging  [27, 43]\n",
            "merging  [14, 27, 43, 46]\n",
            "[57, 41, 45, 21, 70]\n",
            "[57, 41]\n",
            "[57]\n",
            "merging  [57]\n",
            "[41]\n",
            "merging  [41]\n",
            "merging  [41, 57]\n",
            "[45, 21, 70]\n",
            "[45]\n",
            "merging  [45]\n",
            "[21, 70]\n",
            "[21]\n",
            "merging  [21]\n",
            "[70]\n",
            "merging  [70]\n",
            "merging  [21, 70]\n",
            "merging  [21, 45, 70]\n",
            "merging  [21, 41, 45, 57, 70]\n",
            "merging  [14, 21, 27, 41, 43, 45, 46, 21, 70]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RsiCEDJc9-nQ"
      },
      "source": [
        "**4**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZG5iyY967aYF",
        "outputId": "ea7405df-f416-471b-b354-7e3a95027d04"
      },
      "source": [
        "#educative\n",
        "def mergeSort(lst):\n",
        "  if len(lst) > 1:\n",
        "    mid = len(lst) // 2\n",
        "    left = lst[:mid]\n",
        "    right = lst[mid:]\n",
        "\n",
        "  #recursive call for each half\n",
        "    mergeSort(left)\n",
        "    mergeSort(right)\n",
        "\n",
        "    # two iterators for traversing the halves\n",
        "    i = 0\n",
        "    j = 0\n",
        "\n",
        "    # Iterator for the main list\n",
        "    k = 0\n",
        "\n",
        "    while i < len(left)  and j < len(right):\n",
        "      if left[i] < right[j]:\n",
        "        # the value from the left half has been used\n",
        "        lst[k] = left[i]\n",
        "        # move the iterator forward\n",
        "        i += 1\n",
        "      else:\n",
        "        lst[k] = right[j]\n",
        "        j += 1\n",
        "      # move to the next slot\n",
        "      k += 1\n",
        "\n",
        "    # for all the remaining values\n",
        "    while i < len(left):\n",
        "      lst[k] = left[i]\n",
        "        # move the iterator forward\n",
        "      i += 1\n",
        "      k += 1\n",
        "\n",
        "    while j < len(right):\n",
        "      lst[k] = right[j]\n",
        "      j += 1\n",
        "      k += 1\n",
        "\n",
        "lst = [54,26,93,17,77,31,44,55,20]\n",
        "mergeSort(lst)\n",
        "print(lst)\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z35hKsdkAq1U"
      },
      "source": [
        "Algorithm paradigm - divide and conquer"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "r3jSr2Pc_89C",
        "outputId": "61d525a0-3be9-44b5-83b7-ab94b772b6ff"
      },
      "source": [
        "#practice\n",
        "def mergeSort(array):\n",
        "  if len(array) > 1:\n",
        "    mid = len(array) // 2\n",
        "    left = array[:mid]\n",
        "    right = array[mid:]\n",
        "\n",
        "    mergeSort(left)\n",
        "    mergeSort(right)\n",
        "\n",
        "    i = j = k = 0\n",
        "\n",
        "    while i < len(left) and j < len(right):\n",
        "      if left[i] < right[j]:\n",
        "        array[k] = left[i]\n",
        "        i += 1\n",
        "      else:\n",
        "        array[k] = right[j]\n",
        "        j += 1\n",
        "      k += 1\n",
        "\n",
        "    while i < len(left):\n",
        "      array[k] = left[i]\n",
        "      i += 1\n",
        "      k += 1\n",
        "    while j < len(right):\n",
        "      array[k] = right[j]\n",
        "      j += 1\n",
        "      k += 1\n",
        "  \n",
        "array = [4, 2, 1, 3, 8, 6, 5]\n",
        "mergeSort(array)\n",
        "print(array)"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5, 6, 8]\n"
          ]
        }
      ]
    }
  ]
}