fork download
copy 
  1. def count_inversion(alist):
  2.     count = 0
  3.     if len(alist)>1:
  4.         mid = len(alist)//2
  5.         lefthalf = alist[:mid]
  6.         righthalf = alist[mid:]
  7.         # streo inversion count 
  8.         count+=count_inversion(lefthalf)
  9.         count+=count_inversion(righthalf)
  10.  
  11.         i=0
  12.         j=0
  13.         k=0
  14.         track = 0
  15.         while i < len(lefthalf) and j < len(righthalf):
  16.             if lefthalf[i] < righthalf[j]:
  17.                 alist[k]=lefthalf[i]
  18.                 i=i+1
  19.  
  20.             else:
  21.                 alist[k]=righthalf[j]
  22.                 j=j+1
  23.                 # updated line
  24.                 count+=len(lefthalf[i:])
  25.             k=k+1
  26.  
  27.         while i < len(lefthalf):
  28.             alist[k]=lefthalf[i]
  29.             i=i+1
  30.             k=k+1
  31.  
  32.         while j < len(righthalf):
  33.             alist[k]=righthalf[j]
  34.             j=j+1
  35.             k=k+1
  36.  
  37.     return count
  38.  
  39. def main():
  40.     alist = [10,9,8,7,6,5,4,3,2,1]
  41.     inversion = count_inversion(alist)
  42.     print(alist)
  43.     print(inversion)    
  44.  
  45. main()
  46.  
Success #stdin #stdout 0.04s 9320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
45
https://ideone.com/EZBQ7s
language:
Python 3 (python  3.12)
created:
7 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!