I think that the best stone for such uses is quartzite, as shown here:
http://www.sandiegodreampools.com/galle ... _tile_fishRegular sandstone is not durable enough for such use. Some sandstone might be suitable depending on the quality and composition. Such sandstone might be referred to as a quartzitic sandstone. Some quartzitic sandstone is sold as quartzite. A true quartzite would work best.
It might be best to consult a stonemason or a stone supplier to inquire about what stones are suitable and available.
Note: Quartz based stones are classified according to ASTM C616 as Type I (Sandstone), Type II (quartzitic sandstone), or Type III (quartzite).
The stone mason and/or supplier should be able to tell you which classification the stone is. There are specific qualities that the stone has to meet to qualify as a particular type.
http://www.astm.org/Standards/C616.htmhttp://www.buildingstoneinstitute.org/s ... tSheet.pdfftp://ftp.ebuild.com/woc/M950530.PDF