Rubyで quicksort (末尾再帰除去)

quicksort.rb

def qsort(nums)
  execute(nums, 0, nums.size - 1)
end

def execute(nums, left, right)
  while left < right
    pivot = partition(nums, left, right)
    if pivot - left <= right - pivot
      execute(nums, left, pivot - 1)
      left = pivot + 1
    else
      execute(nums, pivot + 1, right)
      right = pivot - 1
    end
  end
end

def partition(nums, left, right)
  pivot = get_pivot_index(nums, left, right)
  swap(nums, pivot, right)
  i = left - 1
  for j in left...right
    if nums[j] <= nums[right]
      i += 1
      swap(nums, i, j)
    end
  end
  swap(nums, i + 1, right)
  return i + 1
end

def get_pivot_index(nums, left, right)
  mid = (right - left) / 2 + left

  if nums[left] <= nums[mid]
    return mid if nums[mid] <= nums[right]
    return right if nums[left] <= nums[right]
    return left
  else
    return left if nums[left] <= nums[right]
    return right if nums[mid] <= nums[right]
    return mid
  end
end

def swap(nums, a_idx, b_idx)
  nums[a_idx], nums[b_idx] = nums[b_idx], nums[a_idx]
end