from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(0, len(nums)):
            min_ele = i
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_ele]:
                    min_ele = j
            self.swap(nums, i, min_ele)

    def swap(self, arr: List[int], i: int, j: int) -> None:
        arr[i], arr[j] = arr[j], arr[i]

from typing import List

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            # Flag to check if any swaps were made in this pass
            swapped = False
            for j in range(0, n-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                    swapped = True
            # If no swaps were made, the array is already sorted
            if not swapped:
                break

        return nums

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(0, len(nums)):
            j = i
            while(j > 0 and nums[j-1] > nums[j]):
                nums[j-1], nums[j] = nums[j], nums[j-1]
                j -= 1

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    merged = []
    l, r = 0, 0

    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1

    merged += left[l:] + right[r:]
    return merged

# Quick sort in Python

# function to find the partition position
def partition(array, low, high):

  # choose the rightmost element as pivot
  pivot = array[high]

  # pointer for greater element
  i = low - 1

  # traverse through all elements
  # compare each element with pivot
  for j in range(low, high):
    if array[j] <= pivot:
      # if element smaller than pivot is found
      # swap it with the greater element pointed by i
      i = i + 1

      # swapping element at i with element at j
      (array[i], array[j]) = (array[j], array[i])

  # swap the pivot element with the greater element specified by i
  (array[i + 1], array[high]) = (array[high], array[i + 1])

  # return the position from where partition is done
  return i + 1

# function to perform quicksort
def quickSort(array, low, high):
  if low < high:

    # find pivot element such that
    # element smaller than pivot are on the left
    # element greater than pivot are on the right
    pi = partition(array, low, high)

    # recursive call on the left of pivot
    quickSort(array, low, pi - 1)

    # recursive call on the right of pivot
    quickSort(array, pi + 1, high)