A methodology for distributing the process of feature selection based on several data complexity measures is proposed. We tackled the two strategies to partition the datasets: horizontal (i.e. by samples) and vertical (i.e. by features). We present an experimental study on 11 datasets (five of them microarrays) in terms of number of selected features, classification accuracy and running time. The novel procedures are able to reduce significantly the running time while maintaining (or even improving) the classification performance.