fork download
copy 
  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.         if i > mid:
  13.             a[k] = aux[j]
  14.             j += 1
  15.         elif j > hi:
  16.             a[k] = aux[i]
  17.             i += 1
  18.         elif aux[i] < aux[j]:
  19.             a[k] = aux[i]
  20.             i += 1
  21.         else:
  22.             a[k] = aux[j]
  23.             j += 1
  24.     assert isSorted(a, lo, hi)
  25.  
  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-1):
  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. def main():
  53.     arr = [3, 7, 2, 8, 14, 20, 5, 19, 10, 17, 1, 16, 11, 18, 12, 9, 13, 4, 15, 6]
  54.     #arr = [3, 2, 5, 1, 4]
  55.     merge_sort(arr)
  56.     print(arr)
  57.  
  58. if __name__ == "__main__":
  59.     main()
Success #stdin #stdout 0.1s 10088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
https://ideone.com/tX3ewN
language:
Python 3 (python  3.9.5)
created:
9 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!