merge_sort.nim

proc mergeSort[T](arr: var seq[T]) =
  # Check if the array has more than one element
  if arr.len <= 1:
    return

  # Calculate mid index
  let mid = arr.len div 2

  # Split the array into two halves
  var leftHalf = arr[0 ..< mid]
  var rightHalf = arr[mid ..< arr.len]

  # Recursively sort the two halves
  mergeSort(leftHalf)
  mergeSort(rightHalf)

  # Merge the sorted halves
  var i = 0
  var j = 0
  var k = 0
  while i < leftHalf.len and j < rightHalf.len:
    if leftHalf[i] <= rightHalf[j]:
      arr[k] = leftHalf[i]
      inc(i)
    else:
      arr[k] = rightHalf[j]
      inc(j)
    inc(k)

  # Copy the remaining elements of leftHalf, if any
  while i < leftHalf.len:
    arr[k] = leftHalf[i]
    inc(i)
    inc(k)

  # Copy the remaining elements of rightHalf, if any
  while j < rightHalf.len:
    arr[k] = rightHalf[j]
    inc(j)
    inc(k)

# Example script
var nums = @[38, 27, 43, 3, 9, 82, 10]
echo "Original array:", nums
mergeSort(nums)
echo "Sorted array:", nums