如何在Ruby中实现链表的合并排序

class ListNode
  attr_accessor :value, :next

  def initialize(value)
    @value = value
    @next = nil
  end
end

def create_linked_list(arr)
  head = ListNode.new(arr[0])
  current = head

  (1...arr.length).each do |i|
    node = ListNode.new(arr[i])
    current.next = node
    current = node
  end

  head
end

def merge_sort(head)
  return head if head.nil? || head.next.nil?

  mid = find_middle(head)
  left = head
  right = mid.next
  mid.next = nil

  merge(merge_sort(left), merge_sort(right))
end

def find_middle(head)
  slow = head
  fast = head

  while fast.next && fast.next.next
    slow = slow.next
    fast = fast.next.next
  end

  slow
end

def merge(left, right)
  dummy = ListNode.new(0)
  current = dummy

  while left && right
    if left.value < right.value
      current.next = left
      left = left.next
    else
      current.next = right
      right = right.next
    end
    current = current.next
  end

  current.next = left if left
  current.next = right if right

  dummy.next
end

def test_merge_sort(arr)
  head = create_linked_list(arr)
  sorted_head = merge_sort(head)
  print_linked_list(sorted_head)
end

def print_linked_list(head)
  current = head
  while current
    print "#{current.value} "
    current = current.next
  end
  puts
end

test_merge_sort([4, 2, 1, 3])  # 输出：1 2 3 4