def compare_items_element(item1, item2, elem_idx)  
  ch_item1 = item1[elem_idx]
  ch_item2 = item2[elem_idx]

  if !ch_item1 && !ch_item2
    nil
  elsif !ch_item1
    1
  elsif !ch_item2
    -1
  else
    ch_item1 <=> ch_item2
  end

end

def radix_exchange_recurse(array, start_idx, end_idx, curr_char_idx)
  # If start index is equal or higher from end_idx, it doesn't need to sort
  return if start_idx >= end_idx

  # If all elements' nth char. is nil, sort for current range(set) is complete
  all_nil = true
  (start_idx..end_idx).each do |idx|
    all_nil = nil if array[idx][curr_char_idx]
  end

  return if all_nil

  # sort by current character index
  quicksort(array, start_idx, end_idx) do |item1, item2|
    compare_items_element(item1, item2, curr_char_idx)
  end

  p "#{start_idx} ~ #{end_idx} step end... current array is \'#{array.join " "}\'"

  # grouping and re-sort
  last_char = array[start_idx][curr_char_idx]
  char_group_start_idx = start_idx

  ((start_idx + 1)..end_idx).each do |idx2|
    if array[idx2][curr_char_idx] != last_char
      radix_exchange_recurse(array, char_group_start_idx, idx2 - 1,
        curr_char_idx+1)

      last_char = array[idx2][curr_char_idx]
      char_group_start_idx = idx2
    end

  end

  # last group
  radix_exchange_recurse(array, char_group_start_idx, end_idx,
        curr_char_idx+1)
end

def radix_exchange_sort(array)
  radix_exchange_recurse(array, 0, array.length - 1, 0)
end

def quicksort(array, begin_idx, end_idx, &compare_block)
  return if begin_idx >= end_idx

  #p "Quicksorting #{begin_idx} to #{end_idx}..."

  pivot_idx = partition(array, begin_idx, end_idx, &compare_block)

  #p "Pivot is #{pivot_idx}"

  quicksort(array, begin_idx, pivot_idx - 1, &compare_block)
  quicksort(array, pivot_idx + 1, end_idx, &compare_block)

end

def partition(array, begin_idx, end_idx)
  pivot_idx = begin_idx
  pivot = array[pivot_idx]

  left_idx = begin_idx + 1
  right_idx = end_idx

  while left_idx <= right_idx

    while left_idx <= end_idx && yield(array[left_idx], array[pivot_idx]) <= 0
      left_idx += 1
    end

    while right_idx >= begin_idx && yield(array[right_idx], array[pivot_idx]) > 0
      right_idx -= 1
    end

    if left_idx <= right_idx
      array[left_idx], array[right_idx] = array[right_idx], array[left_idx]
    end

  end

  array[pivot_idx], array[right_idx] = array[right_idx], array[pivot_idx]

  #p "Partition End : pivot_idx is #{right_idx} / #{array.join(" ")}"

  right_idx
end

def make_example_array
  %w(add cab fee bad dad bee bed ace)
end

array = make_example_array
p array
radix_exchange_sort(array)
p array