Code used for http://pivotallabs.com/sidekiq-divide-conquer/

20130520015455_create_temp_arrays.rb

class CreateTempArrays < ActiveRecord::Migration
  def change
    create_table :temp_arrays do |t|
      t.string :array
      t.boolean :sorted
      t.integer :parent_id, :integer

      t.timestamps
    end
  end
end

merge_sort_worker.rb

require 'sidekiq'

class MergeSortWorker
  include Sidekiq::Worker

  def perform(array)
    SortWorker.perform_async TempArray.create(array: array).id
  end
end

merge_worker.rb

require 'sidekiq'

class MergeWorker
  include Sidekiq::Worker

  def finish(parent)
    if parent.parent
      MergeWorker.perform_async parent.parent.id
    else
      s = Redis::Semaphore.new(:creating_sorted_array, :connection => "localhost")
      s.lock do
        parent.reload rescue return
        SortedArray.create array: parent.array
        parent.destroy
      end
    end
  end

  def perform(parent_id)
    parent = TempArray.includes(:parent).where(id: parent_id).first
    return if parent.nil?

    finish(parent) and return if parent.sorted?

    if parent.children.present? && parent.children.all?(&:sorted?)
      left = parent.children.first.array
      right = parent.children.last.array
      parent.children.destroy_all

      parent.array = MergesArrays.merge left, right
      parent.sorted = true
      parent.save

      finish parent
    end
  end
end

merges_arrays.rb

class MergesArrays
  def self.merge(left, right)
    sorted = []

    until left.empty? || right.empty?
      if left.first <= right.first
        sorted << left.shift
      else
        sorted << right.shift
      end
    end

    sorted + left + right
  end
end

sort_worker.rb

require 'sidekiq'

class SortWorker
  include Sidekiq::Worker

  def finish(temp_array)
    temp_array.sorted = true
    temp_array.save
    MergeWorker.perform_async temp_array.parent.id
  end

  def perform(array_id)
    temp_array = TempArray.find array_id
    array = temp_array.array

    finish(temp_array) and return if array.count <= 1

    left, right = SplitsArray.split(array)
    temp_left = temp_array.children.create(array: left, sorted: false)
    temp_right = temp_array.children.create(array: right, sorted: false)

    SortWorker.perform_async temp_left.id
    SortWorker.perform_async temp_right.id
  end
end

sorted_array.rb

class SortedArray
  def self.create(*args)
    puts "--------------------"
    puts "Saving:"
    ap args
    puts "--------------------"
  end
end

splits_arrays.rb

class SplitsArray
  def self.split(array)
    middle = array.count / 2
    left  = array[0, middle]
    right = array[middle, (array.count - middle)]
    [left, right]
  end
end

temp_array.rb

class TempArray < ActiveRecord::Base
  serialize :array, Array
  belongs_to :parent, class_name: TempArray, foreign_key: 'parent_id'
  has_many :children, class_name: TempArray, foreign_key: 'parent_id'
end