# 10.6. Sort big file

> Given a 20GB file with one string per line, sort the file.

I would distribute the file in many machines and do a sort of MapReduce, sort each portion separatedly (map) and then join merged files (reduce). Should take O(n log(n)) for each portion, and then O(n) to merge sorted files? This would me a **merge sort**.

A **quick sort** could also work, picking a random element in the array and partition the array around it, such that all numbers lower than the partitioning element come before all elements greater than it

## Solution

If an interviewer gives such a high data size, it's implying **you cannot have all this data in memory**.

Divide the file into chunks which are XMBs big, where X is the amount of memory we have available. Each chunk is sorted separately and then saved back to the file system. Then we merge the chunks one by one. This is known as **external sort**.