I need to hold values in sorted hash in ruby (1.8.7). What data structed will fit the best?
There is nothing in the core library or the standard library now, that will fit your bill.
There is, however, a feature request to add a Red/Black-Tree implementation to Ruby 1.9.3/2.0.
If you are able to force your users to only ever use XRuby or JRuby, you could just use one of the implementations of Java's java.util.SortedMap<K, V> such as java.util.TreeMap<K, V>.
If you are able to force your users to only ever use Ruby.NET or IronRuby, you could just use .NET's System.Collections.Generic.SortedDictionary<TKey, TValue>.
If you are able to force your users to only ever use MRI or YARV, you could use the Ruby/RBTree library. It might also work on Rubinius or the not-yet-released JRuby 1.6. Note that there seem to be multiple independent updated forks of that library in the wild. It is not obvious, which one of those is the most recent and/or best maintained one.
The only solution I know of which is guaranteed to be portable, is Kanwei Li's Algorithms and Containers GSoC 2008 project, which actually contains two implementations of a sorted, key-indexed collection: Containers::RBTreeMap based on a Red/Black-Tree and Containers::SplayTreeMap based on a Splay Tree.