1. A method of enhancing performance of an application executing in a parallel processor, the method comprising: partitioning input into blocks having a block size, wherein the block size has been selected to enable partial sorting of the input; partially sorting the input within each block; and executing the application with the partially sorted input, wherein the block size is determined by: partitioning the input into blocks having a first block size; estimating a value of a performance metric for the application with the input partially sorted within each of the blocks having the first block size; repeating the partitioning and the estimating with a plurality of distinct block sizes, thereby obtaining a plurality of performance metric values; and choosing a desired performance metric value among the plurality of performance metric values and designating a block size corresponding to the desired performance metric as the block size.