Into what format do I need to reformat my External HardDrive for use in Mac OS X, Windows, Linux.
Also, can I have the differences of each partition format, I mean the advantages and disadvantages of each type of format over the others?
Without any additional software, Windows is your limiting factor. Windows can only do FAT, NTFS, exFAT for PC use. Of them, the fastest and best performance is NTFS which is the what the most Windows based file systems have. FAT32/64 is good for small drives like flash but hard drives in general are all NTFS. For more on this, please refer to File Systems. Also to be noted, all modern Linux and Mac systems can read all of the above formats while, as I mentioned, Windows natively is limited (which could be on purpose)
Based on your comment, I would recommend FAT32! You can format external hard drives that are 2TB or less into one FAT32 partition. FAT32 should be recognized on Windows, Mac, and Linux.
Also, to better answer your question, one advantage of NTFS is that it supports volumes larger than 2TB. However, NTFS volumes are read-only on Mac (you will not be able to write to them). I have a 2TB Western Digital external drive that I have reformatted to FAT32 for use with Windows and Mac.
First of all refer to this site to see the major differences between NTFS and FAT http://www.guidingtech.com/11205/difference-between-ntfs-and-fat-32-file-systems/
Second of all please be aware that MacOS doesn't support write on NTFS partition so you need to use FAT32 for Mac writing.