



"""simple docstring"""





def      a__			(   lowerCAmelCase__   ):
      UpperCAmelCase_    				=							0
      UpperCAmelCase_    				=							len(lowerCAmelCase__   )

      for i in range(n - 1   ):
            for j in range(i + 1			,    lowerCAmelCase__   ):
                  if arr[i] > arr[j]:
                        num_inversions += 1

      return num_inversions
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) <= 1:
            return arr, 0
      UpperCAmelCase_    				=							len(lowerCAmelCase__   ) // 2
      UpperCAmelCase_    				=							arr[0:mid]
      UpperCAmelCase_    				=							arr[mid:]

      UpperCAmelCase_				,					UpperCAmelCase_    				=							count_inversions_recursive(lowerCAmelCase__   )
      UpperCAmelCase_				,					UpperCAmelCase_    				=							count_inversions_recursive(lowerCAmelCase__   )
      UpperCAmelCase_				,					UpperCAmelCase_    				=							_count_cross_inversions(lowerCAmelCase__			,    lowerCAmelCase__   )

      UpperCAmelCase_    				=							inversion_p + inversions_q + cross_inversions
      return c, num_inversions
def      a__			(   lowerCAmelCase__			,    lowerCAmelCase__   ):
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_    				=							UpperCAmelCase_    				=							UpperCAmelCase_    				=							0
      while i < len(lowerCAmelCase__   ) and j < len(lowerCAmelCase__   ):
            if p[i] > q[j]:
                  # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
                  # These are all inversions. The claim emerges from the
                  # property that P is sorted.
                  num_inversion += len(lowerCAmelCase__   ) - i
                  r.append(q[j]   )
                  j += 1
            else:
                  r.append(p[i]   )
                  i += 1

      if i < len(lowerCAmelCase__   ):
            r.extend(p[i:]   )
      else:
            r.extend(q[j:]   )

      return r, num_inversion
def      a__			(   ):
      UpperCAmelCase_    				=							[10, 2, 1, 5, 5, 2, 11]

      # this arr has 8 inversions:
      # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

      UpperCAmelCase_    				=							count_inversions_bf(lowerCAmelCase__   )
      UpperCAmelCase_				,					UpperCAmelCase_    				=							count_inversions_recursive(lowerCAmelCase__   )

      assert num_inversions_bf == num_inversions_recursive == 8

      print("number of inversions = "			,    lowerCAmelCase__   )

      # testing an array with zero inversion (a sorted arr_1)

      arr_a.sort()
      UpperCAmelCase_    				=							count_inversions_bf(lowerCAmelCase__   )
      UpperCAmelCase_				,					UpperCAmelCase_    				=							count_inversions_recursive(lowerCAmelCase__   )

      assert num_inversions_bf == num_inversions_recursive == 0
      print("number of inversions = "			,    lowerCAmelCase__   )

      # an empty list should also have zero inversions
      UpperCAmelCase_    				=							[]
      UpperCAmelCase_    				=							count_inversions_bf(lowerCAmelCase__   )
      UpperCAmelCase_				,					UpperCAmelCase_    				=							count_inversions_recursive(lowerCAmelCase__   )

      assert num_inversions_bf == num_inversions_recursive == 0
      print("number of inversions = "			,    lowerCAmelCase__   )


if __name__ == "__main__":
  main()









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) == 0:
            return []
      UpperCAmelCase_				,					UpperCAmelCase_    				=							min(lowerCAmelCase__   ), max(lowerCAmelCase__   )
      UpperCAmelCase_    				=							int(max_value - min_value   ) + 1
      UpperCAmelCase_    				=							[[] for _ in range(lowerCAmelCase__   )]

      for i in my_list:
            buckets[int(i - min_value   )].append(lowerCAmelCase__   )

      return [v for bucket in buckets for v in sorted(lowerCAmelCase__   )]


if __name__ == "__main__":
  from doctest import testmod

  testmod()
  assert bucket_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
  assert bucket_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]




