CODEWITHSUNDEEP
time-complexityarray-algorithms
ako
ako

Reputation: 2681

sorting a file containing huge amount of data

Consider a file containing N words with one word per line.The file is too big so whole of it connot be read in memory at one time.
My ans: Divide the file into k chunks.So size of each chunk x = N/k
Read one chunk into memory at a time and sort it and write back to the file.Sort all k chunks.
Now do a k way merge.
Analying total time complexity. How can i do it?
Time for sorting each chunk = xlogx (assuming i use quick sort)
Time for merging k chunks = klogk (is it??)
So total time complexity =??
Am week at analying time complexity

Upvotes: 1

Views: 196

Answers (1)

Pavan Dittakavi
Pavan Dittakavi

Reputation: 3181

Each chunk is of size N/k and the number of chunks is k.

So, total time complexity would be

Reading of N/k chunks + Sorting each of those chunks i.e., O( N/k klogk) + Merging each [part] of those k chunks O( Nk ) + File Writing.

So, it would be IO Time + O(Nlogk)

I am learning these things too...so it would be great if someone can analyze and correct me if im wrong here..

-Pavan.

Upvotes: 1

Related Questions