CareerCup

external sort

Another way to do this is use to Parallel Processing frameworks like Map/Reduce.

video.google.com/videoplay?docid=-978892635109400080

What's a query?
Generally, divide input into 1000 batches, sort and output to different files. Then merge consecutively.

or Radix sort (More complicated)

Bucket Sort would be the way to go or you can also use InsSort (Merge+Insertion).

N-Way Merge Sort

first devide the array into size of cache.sort each array separately and then apply merge sort in group of two recursively

I think Redix sort and Bucket sort can be performed until we know what kind of data is in file. Redix sort can be done if data is integer and Bucket sort can be done if data is in certain range.

I was wondering if Bit Vectors can be used?

I was wondering if Bit Vectors can be used?

hello friends for this we don't need external sorting
10,00,000 instructions
1,000 at a time can sort
if we divide 10,00,000 instructions into 500 blocks
first sort first 2 block
then take last 500 sorted instruction and next 500 unsorted instructions ...sort them
now take first 500 sorted instruction of last sorted instruction and and above 500 instruction and sort them now we have 1500 sorted instruction similarly take next 500 instruction and make 2,000 sorted instruction and so on

for example
we have 16 integer and at a time i can take only 4 integer in memory and can perform sorting over then
5,6,1,3,2,3,1,1,7,6,3,8,8,7,6,5
divide them in block of 2 so it become
[5,6],[1,3],[2,3],[1,1],[7,6],[3,8],[8,7],[6,5]
now take first 2 block and sort them
[1,3],[5,6].......rest are unsorted
now take last sorted block and next unsorted block
and sort them
[1,3][2,3][5,6].....
then recursively sort the previous 2 blocks ([1,3]&[2,3]) until no block to sorted
1,2,3,3,5,6(sorted)........unsorted rest blocks
similarly extend it and finally u get all sorted list

thank u
i hope u understand