


from __future__ import annotations



def      _lowerCAmelCase  (							lowerCAmelCase_							:list[int]							)->list[int]:
   '''simple docstring'''






   if not list_of_ints:
      return []

   if min(lowerCAmelCase_							) < 0:
      raise ValueError("All numbers must be positive"							)

   snake_case_         =   max(len(bin(lowerCAmelCase_							)[2:]							) for x in list_of_ints							)
   return _msd_radix_sort(lowerCAmelCase_						,  lowerCAmelCase_							)



def      _lowerCAmelCase  (							lowerCAmelCase_							:list[int]						,  lowerCAmelCase_							:int							)->list[int]:
   '''simple docstring'''






   if bit_position == 0 or len(lowerCAmelCase_							) in [0, 1]:
      return list_of_ints

   snake_case_         =   []
   snake_case_         =   []
   # Split numbers based on bit at bit_position from the right
   for number in list_of_ints:
      if (number >> (bit_position - 1)) & 1:
         # number has a one at bit bit_position
         ones.append(lowerCAmelCase_							)
      else:
         # number has a zero at bit bit_position
         zeros.append(lowerCAmelCase_							)

    # recursively split both lists further
   snake_case_         =   _msd_radix_sort(lowerCAmelCase_						,  bit_position - 1							)
   snake_case_         =   _msd_radix_sort(lowerCAmelCase_						,  bit_position - 1							)

   # recombine lists
   snake_case_         =   zeros
   res.extend(lowerCAmelCase_							)

   return res



def      _lowerCAmelCase  (							lowerCAmelCase_							:list[int]							)->Dict:
   '''simple docstring'''






   snake_case_         =   len(lowerCAmelCase_							)
   if not list_of_ints or length == 1:
      return

   if min(lowerCAmelCase_							) < 0:
      raise ValueError("All numbers must be positive"							)

   snake_case_         =   max(len(bin(lowerCAmelCase_							)[2:]							) for x in list_of_ints							)
   _msd_radix_sort_inplace(lowerCAmelCase_						,  lowerCAmelCase_						,  0						,  lowerCAmelCase_							)



def      _lowerCAmelCase  (							lowerCAmelCase_							:list[int]						,  lowerCAmelCase_							:int						,  lowerCAmelCase_							:int						,  lowerCAmelCase_							:int							)->Tuple:
   '''simple docstring'''






   if bit_position == 0 or end_index - begin_index <= 1:
      return

   bit_position -= 1

   snake_case_         =   begin_index
   snake_case_         =   end_index - 1
   while i <= j:
      snake_case_         =   False
      if not (list_of_ints[i] >> bit_position) & 1:
         # found zero at the beginning
         i += 1
         snake_case_         =   True
      if (list_of_ints[j] >> bit_position) & 1:
         # found one at the end
         j -= 1
         snake_case_         =   True

      if changed:
         continue

      snake_case_      ,      snake_case_         =   list_of_ints[j], list_of_ints[i]
      j -= 1
      if j != i:
         i += 1

   _msd_radix_sort_inplace(lowerCAmelCase_						,  lowerCAmelCase_						,  lowerCAmelCase_						,  lowerCAmelCase_							)
   _msd_radix_sort_inplace(lowerCAmelCase_						,  lowerCAmelCase_						,  lowerCAmelCase_						,  lowerCAmelCase_							)


if __name__ == "__main__":
   import doctest

   doctest.testmod()








from __future__ import annotations



def      _lowerCAmelCase  (							lowerCAmelCase_							:int							)->list[int]:
   '''simple docstring'''






   assert (
       isinstance(lowerCAmelCase_						,  lowerCAmelCase_							) and mask > 0
   ), F'''mask needs to be positive integer, your input {mask}'''
   snake_case_         =   []
   snake_case_         =   mask

   while submask:
      all_submasks.append(lowerCAmelCase_							)
      snake_case_         =   (submask - 1) & mask

   return all_submasks


if __name__ == "__main__":
   import doctest

   doctest.testmod()




