A block of a video data stream may be subject to a motion search for comparing inter prediction of the blocks to intra prediction of the block while being partitioned. A motion search using an initial search range finds a first motion vector for the block. The blocks is partitioned into at least two sub-blocks, each having a same size, and one or more motion searches are performed for each sub-block using a second search range and the first motion vector where the second search range is a fraction of the initial search range. Respective error values associated with each of the motion searches are compared to select a partition for coding the block, and the block may be encoded using the selected partition. Performing inter prediction in this fashion can improve the performance of an encoder in terms of both execution time and compression ratio.