

from __future__ import annotations

import re

def      a__	(						UpperCAmelCase				:     list[str]     )    ->		list[str]:

  def alphanum_key(UpperCAmelCase				:     int     ):
    return [int(UpperCAmelCase     ) if s.isdigit() else s.lower() for s in re.split('''([0-9]+)'''							,					UpperCAmelCase     )]

  return sorted(UpperCAmelCase							,					key=UpperCAmelCase     )


if __name__ == "__main__":
     import doctest

     doctest.testmod()








def      a__	(						UpperCAmelCase				:     list     )    ->		list:
  UpperCAmelCase			:				Tuple										=					len(UpperCAmelCase     )

  # Set the gap value to be decreased by a factor of 1.3
  # after each iteration
  UpperCAmelCase			:				Optional[Any]										=					1.3

  # Continue sorting until the gap is 1
  while gap > 1:
    # Decrease the gap value
    UpperCAmelCase			:				int										=					int(gap / shrink     )

    # Sort the elements using insertion sort
    for i in range(UpperCAmelCase							,					len(UpperCAmelCase     )     ):
      UpperCAmelCase			:				Union[str, Any]										=					collection[i]
      UpperCAmelCase			:				List[Any]										=					i
      while j >= gap and collection[j - gap] > temp:
        UpperCAmelCase			:				int										=					collection[j - gap]
        j -= gap
      UpperCAmelCase			:				List[Any]										=					temp

  return collection


if __name__ == "__main__":
     import doctest

     doctest.testmod()





