merge sort (in-place)

merge-sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# merge-sort\n",
    "\n",
    "import math\n",
    "\n",
    "def merge(arr, l, r, q):\n",
    "    arrc_l = arr[l:q + 1]\n",
    "    arrc_r = arr[q + 1:r + 1]\n",
    "    arrc_l.append(math.inf)\n",
    "    arrc_r.append(math.inf)\n",
    "    j = k = 0\n",
    "    for i in range(l, r + 1):\n",
    "        if arrc_l[j] < arrc_r[k]:\n",
    "            arr[i] = arrc_l[j]\n",
    "            j += 1\n",
    "        else:\n",
    "            arr[i] = arrc_r[k]\n",
    "            k += 1\n",
    "\n",
    "def merge_sort(arr, l, r):\n",
    "    if l >= r:\n",
    "        return\n",
    "    q = (l + r) // 2\n",
    "    merge_sort(arr, l, q)\n",
    "    merge_sort(arr, q + 1, r)\n",
    "    merge(arr, l, r, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# merge-sort (in-place)\n",
    "# http://blog.csdn.net/acdreamers/article/details/24244643\n",
    "\n",
    "import math\n",
    "\n",
    "def rev_mem(arr, l, r):\n",
    "    while l < r:\n",
    "        arr[l], arr[r] = arr[r], arr[l]\n",
    "        r -= 1\n",
    "        l += 1\n",
    "\n",
    "def exch_mem(arr, l, r, q):\n",
    "    rev_mem(arr, l, q)\n",
    "    rev_mem(arr, q + 1, r)\n",
    "    rev_mem(arr, l, r)\n",
    "\n",
    "def merge_inplace(arr, l, r, q):\n",
    "    i = l\n",
    "    j = q + 1\n",
    "    while i < j and j <= r:\n",
    "        while i < j and arr[i] <= arr[j]: i += 1\n",
    "        tmp = j\n",
    "        while j <= r and arr[j] < arr[i]: j += 1\n",
    "        exch_mem(arr, i, j - 1, tmp - 1)\n",
    "        i += j - tmp\n",
    "\n",
    "def merge_sort_inplace(arr, l, r):\n",
    "    if l >= r:\n",
    "        return\n",
    "    q = (l + r) // 2\n",
    "    merge_sort(arr, l, q)\n",
    "    merge_sort(arr, q + 1, r)\n",
    "    merge_inplace(arr, l, r, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# quick-sort\n",
    "\n",
    "import random\n",
    "import math\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(10000000)\n",
    "\n",
    "def quick(arr, l, r):\n",
    "    u = q = l\n",
    "    # arr[(r+l)//2], arr[r] = arr[r], arr[(r+l)//2]\n",
    "    while u < r:\n",
    "        if arr[u] < arr[r]:\n",
    "            arr[u], arr[q] = arr[q], arr[u]\n",
    "            q += 1\n",
    "        u += 1\n",
    "    arr[r], arr[q] = arr[q], arr[r]\n",
    "    return q\n",
    "\n",
    "def quick_sort(arr, l, r):\n",
    "    if l >= r:\n",
    "        return\n",
    "    q = quick(arr, l, r)\n",
    "    quick_sort(arr, l, q-1)\n",
    "    quick_sort(arr, q+1, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merge sort:\n",
      "CPU times: user 1.01 s, sys: 1 ms, total: 1.01 s\n",
      "Wall time: 1.01 s\n",
      "\n",
      "merge sort (in-place):\n",
      "CPU times: user 4min 29s, sys: 11 ms, total: 4min 29s\n",
      "Wall time: 4min 29s\n",
      "\n",
      "quick sort:\n",
      "CPU times: user 930 ms, sys: 0 ns, total: 930 ms\n",
      "Wall time: 929 ms\n",
      "\n",
      " True\n"
     ]
    }
   ],
   "source": [
    "arr_num, arr_rng = 10 ** 5, (1, 10 ** 5)\n",
    "\n",
    "testarr = [random.randint(*arr_rng) for i in range(arr_num)]\n",
    "copy1 = testarr[:]\n",
    "copy2 = testarr[:]\n",
    "copy3 = testarr[:]\n",
    "\n",
    "print(\"merge sort:\")\n",
    "%time merge_sort(copy1, 0, len(testarr) - 1)\n",
    "\n",
    "print(\"\\nmerge sort (in-place):\")\n",
    "%time merge_sort_inplace(copy2, 0, len(testarr) - 1)\n",
    "\n",
    "print(\"\\nquick sort:\")\n",
    "%time quick_sort(copy3, 0, len(testarr) - 1)\n",
    "\n",
    "print(\"\\n\", copy1 == copy2 == copy3)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:py3]",
   "language": "python",
   "name": "conda-env-py3-py"
  },
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}