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_start_idx, pivot_end_idx =
    partition(array, begin_idx, end_idx, &compare_block)

  #p "Pivot is #{pivot_idx}"

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

end

# 3-group partition
# less than pivot, equal to pivot, higher than pivot
# http://blogs.microsoft.co.il/blogs/eyal/archive/2009/02/15/interview-question-6-three-way-partition-generic-solution.aspx
def partition(array, begin_idx, end_idx)
  pivot_idx = begin_idx
  pivot = array[pivot_idx]

  first_p = second_p = pivot_idx + 1
  third_p = end_idx

  while second_p <= third_p
    comp_val = yield(array[second_p], array[pivot_idx])

    if comp_val > 0
      # move to the third partition
      array[second_p], array[third_p] = array[third_p], array[second_p]
      third_p -= 1
    elsif comp_val < 0
      # move to the first partition
      array[first_p], array[second_p] = array[second_p], array[first_p]
      first_p += 1
      second_p += 1
    else
      # leave in the second partition
      second_p += 1
    end

  end

  # move pivot to second partiton's first position
  array[pivot_idx], array[first_p - 1] =
    array[first_p - 1], array[pivot_idx]

  return first_p - 1, third_p
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