fork(1) download 
  1. import math
  2.  
  3. def merge(a, aux, lo, mid, hi):
  4.     assert isSorted(a, lo, mid)
  5.     assert isSorted(a, mid+1, hi)
  6.  
  7.     for k in range(lo, hi+1):
  8.         aux[k] = a[k]
  9.  
  10.     i, j = lo, mid + 1
  11.     for k in range(lo, hi+1):
  12.         print("i = ",i, ", j = ",j)
  13.         if i > mid:
  14.             a[k] = aux[j]
  15.             j += 1
  16.         elif j > hi:
  17.             a[k] = aux[i]
  18.             i += 1
  19.         elif aux[i] < aux[j]:
  20.             a[k] = aux[i]
  21.             i += 1
  22.         else:
  23.             a[k] = aux[j]
  24.             j += 1
  25.     assert isSorted(a, lo, hi)    
  26.  
  27. def sort(a, aux, lo, hi):
  28.     if (lo >= hi): return a
  29.     mid = math.floor(lo + (hi-lo) / 2)
  30.  
  31.     sort(a, aux, lo, mid)
  32.     sort(a, aux, mid+1, hi)
  33.     merge(a, aux, lo, mid, hi)
  34.  
  35. def merge_sort(a):
  36.     aux = [0] * len(a)
  37.     sort(a, aux, 0, len(a)-1)
  38.     assert isSortedArray(a)
  39.  
  40. def isSorted(a, lo, hi):
  41.     for i in range(lo, hi):
  42.         if a[i+1] < a[i]:
  43.             return False
  44.     return True
  45.  
  46. def isSortedArray(a):
  47.     for i in range(0, len(a)-1):
  48.         if a[i+1] < a[i]:
  49.             return False
  50.     return True
  51.  
  52.  
  53. data = [11,1,5,7,9,11,2,3,4,6,0,10]
  54. print data
  55. try:
  56.     merge_sort(data)
  57. except Exception as err:
  58. 	print "Exception in user code: ", err
  59.  
  60. print data
  61.  
Success #stdin #stdout 0.01s 7852KB
comments (?)
stdin 
Standard input is empty
stdout 
[11, 1, 5, 7, 9, 11, 2, 3, 4, 6, 0, 10]
Exception in user code:  range() integer end argument expected, got float.
[11, 1, 5, 7, 9, 11, 2, 3, 4, 6, 0, 10]
https://ideone.com/8ENwXF
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!