title: Sorting huge volumed data using Serialized Binary Search Tree
body: <p>I have 50 GB structured (as key/value) data like this which are stored in a text file (input.txt / keys and values are 63 bit unsigned integers);</p>
  
  <pre><code>3633223656935182015 2473242774832902432
  8472954724347873710 8197031537762113360
  2436941118228099529 7438724021973510085
  3370171830426105971 6928935600176631582
  3370171830426105971 5928936601176631564
  </code></pre>
  
  <p>I need to sort this data as keys in increasing order with the minimum value of that key. The result must be presented in another text file (data.out) under 30 minutes. For example the result must be like this for the sample above;</p>
  
  <pre><code>2436941118228099529 7438724021973510085
  3370171830426105971 5928936601176631564
  3633223656935182015 2473242774832902432
  8472954724347873710 8197031537762113360
  </code></pre>
  
  <p>I decided that; </p>
  
  <ul>
  <li><p>I will create a BST tree with the keys from the input.txt with their minimum value, but this tree would be more than 50GB. I mean, I have time and memory limitation at this point. </p></li>
  <li><p>So I will use another text file (tree.txt) and I will serialize the BST tree into that file.</p></li>
  <li><p>After that, I will traverse the tree using in-order traverse and write the sequenced data into data.out file. </p></li>
  </ul>
  
  <p>My problem is mostly with the serialization and deserialization part. How can I serialize this type of data? and I want to use the INSERT operation on the serialized data. Because my data is bigger than memory. I can't perform this in the memory. Actually I want to use text files as a memory.</p>
  
  <p>By the way, I am very new to this kind of stuffs. If is there a conflict with my algorithm steps, please warn me. Any thought, technique and code samples would be helpful.</p>
  
  <pre><code>OS: Linux
  Language: C
  RAM: 6 GB
  </code></pre>
  
  <p>Note: I am not allowed to use built-in functions like sort and merge. </p>