algorithm - Sort rectangles according to area in O(N) -

let r1,...rn n axis-aligned rectangles in plane corners points in n×n-grid. thus, each rectangle ri 4 corners points both coordinates integers in {1,...n}.

now want sort these rectangles r1,...rn there increasing area in o(n) time.

i have algorithm sort them in o(n*log n). how can done in o(n) ?

using o(n*log n) can :

calculate areas, , sort using standard sorting algorithm quick sort 

i guess per-processing required, can sort in o(n) , because given pre-conditions can help. want algorithm, no code required.

since keys (areas) of rectangles integers, task can completed in o(n) time using counting sort. know minimum key 0 , maximum key problem n^2, in algorithm k=n^2+1. algorithm completes in 3 passes: computing histogram, computing starting , ending indexes each key, copying data output array, preserving order of inputs equal keys sort stable. each pass o(n) altogether algorithm o(n).

example: suppose n 3. k 1 more largest key appears in data, keys fit in range [0..k-1] inclusive, i.e., k 10. make histogram h setting array of 0s index 0 k-1, , fill histogram walking through set of rectangles , count them up. there 2 area 1, 5 area 2, , 2 area 4. h = [0, 2, 5, 0, 2, 0, 0, 0, 0, 0]. starting indexes computed histogram 0, 0, 2, 7, 7, 9, 9, 9, 9, 9. rectangle area 0 goes output array starting @ 0. rectangle area 1 goes output array starting @ 0 (and increment number when put rectangle of area 1 output). rectangle area 2 goes output array starting @ 2. rectangle area 3 goes output array starting @ 7. rectangle area 4 goes output array starting @ 7.