Mergesort Differentiation in Julia.ipynb

mergesort-differentiation-in-julia.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Julia 1.1.1",
      "language": "julia",
      "name": "julia-1.1"
    },
    "language_info": {
      "file_extension": ".jl",
      "mimetype": "application/julia",
      "name": "julia",
      "version": "1.1.1"
    },
    "colab": {
      "name": "Mergesort Differentiation in Julia.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/corba777/48740d91f1d651fe2f2f49e8dfd75711/mergesort-differentiation-in-julia.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dKFtjd2TYRlf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "using Pkg"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BG0G6p3VYRlm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Pkg.add(\"ForwardDiff\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iZVs2HMcYRlr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "using ForwardDiff"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VCxcPH-uYRlu",
        "colab_type": "code",
        "colab": {},
        "outputId": "99e497a0-15a5-4091-9ed7-d727802e3845"
      },
      "source": [
        "function mergesort(arr)\n",
        "    if length(arr) ≤ 1 return arr end\n",
        "    mid = length(arr) ÷ 2\n",
        "    lpart = mergesort(arr[1:mid])\n",
        "    rpart = mergesort(arr[mid+1:end])\n",
        "    rst = []\n",
        "    ri = li = 1\n",
        "    @inbounds while li ≤ length(lpart) && ri ≤ length(rpart)\n",
        "        if lpart[li] < rpart[ri]\n",
        "            push!(rst,lpart[li])\n",
        "            li += 1\n",
        "        else\n",
        "            push!(rst,rpart[ri])\n",
        "            ri += 1\n",
        "        end        \n",
        "    end\n",
        "   \n",
        "    if li <= length(lpart)\n",
        "        append!(rst,lpart[li:length(lpart)])\n",
        "    end\n",
        "    if ri<=length(rpart)\n",
        "        append!(rst,rpart[ri:length(rpart)])\n",
        "    end\n",
        "   \n",
        "    return rst\n",
        "end"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "mergesort (generic function with 2 methods)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XruOQc1_YRlx",
        "colab_type": "code",
        "colab": {},
        "outputId": "4a9e46e7-d9bd-467c-ec7b-dedd6be9a611"
      },
      "source": [
        "v=rand(-10.0:10.0,5)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5-element Array{Float64,1}:\n",
              "  10.0\n",
              " -10.0\n",
              "   4.0\n",
              "  -7.0\n",
              "  -7.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SSkvyDHcYRlz",
        "colab_type": "code",
        "colab": {},
        "outputId": "a429f5d1-c2bc-4526-b3ee-9a40c62e632d"
      },
      "source": [
        "    ForwardDiff.jacobian(x->mergesort(x),v)\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5×5 Array{Any,2}:\n",
              " 0.0  1.0  0.0  0.0  0.0\n",
              " 0.0  0.0  0.0  0.0  1.0\n",
              " 0.0  0.0  0.0  1.0  0.0\n",
              " 0.0  0.0  1.0  0.0  0.0\n",
              " 1.0  0.0  0.0  0.0  0.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 19
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iwqLcZj7YRl2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "Pkg.add(\"ReverseDiff\")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DgKFr5GbYRl5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "using ReverseDiff"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rpKLaQfRYRl9",
        "colab_type": "code",
        "colab": {},
        "outputId": "3e9e6bfc-92a7-4ece-ef74-24141bb53890"
      },
      "source": [
        "ReverseDiff.jacobian(mergesort,v)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5×5 Array{Float64,2}:\n",
              " 0.0  1.0  0.0  0.0  0.0\n",
              " 0.0  0.0  0.0  0.0  1.0\n",
              " 0.0  0.0  0.0  1.0  0.0\n",
              " 0.0  0.0  1.0  0.0  0.0\n",
              " 1.0  0.0  0.0  0.0  0.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "d9XOZqwHYRmB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}