A Better Way to sort a million 32-bit integers in 2MB of RAM


The data of a million 32-bit integers would take up 4 megabytes, assuming binary encoding. So to sort them with minimal memory usage, the sorting algorithm most of people will consider is the MergeSort algorithm. The basic idea is to create a temporary file that is stored in the hard disk. Then read the first 0.5 million integers in the RAM, sort them, and then save them into a temporary file. Afterwards, read the remaining 0.5 million integers in the RAM, sort them, and then save them into another temporary file. Finally, we merge these two temporary files together.


However, there is a better solution without using temporary files (this is proposed by others. see http://news.ycombinator.com/item?id=341037). 


Select the 500.000 smallest values, sort them using an in place sorting algorithm and spit them out, then select the 500.000 biggest values, sort them and spit them out.


The problem then boils down to select the n/2 smallest values of the list. To do this we store the n/2 first values in the 2MB buffer. We then organize them into a heap with the biggest at the top. I then process the remaining n/2 values. When one of these values is bigger than the heap top value, it is skipped. If it is smaller, the heap biggest value is replaced with the smaller value and the heap is restored to get the biggest value at the top. When all the n/2 values have been processed, the 2MB buffer contains the n/2 smallest values of the million integer list.


Since it is already organized as a heap one can use heap sort to sort it. Pick the biggest value at the top and swap it with the last value of the list and restore heap to get the next biggest value at the top. Swap it with the last unsorted value and proceed until the heap length is reduced to one element.

Apply the same algorithm with the n/2 biggest value but using a heap with the smallest value at the top. 


This algorithm requires two passes over the million integer, and uses nothing more than the 2MB buffer. The complexity is O(nlog).

Why do hash functions use prime numbers?

A good blog post for this question: http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Improve Your LIfe

1. Become A Company Leader
Don't try to do everything. Pick your three strongest assets and over-deliver. Of course, those assets will be in line with the boss's wishes and the company's goals, so you'll become a brand that's promoted. Grab any chance to enter competitions or attend industry conferences. When you win an award, remember to thank not only your boss but also the underlings who toiled to make you look good.

2. Run Effortlessly
Instead of counting seconds, count heartbeats. Presetting a time goal, like a 7-minute mile, can undermine your training program because you may push yourself when you shouldn't be pushing. Instead, let how your body feels be your guide. If you train this way, you'll end up achieving the improvements you desire. With this as your norm, push it once a week by running at 90 percent of your maximum heart rate. (To find your max, subtract your age from 220). Sandwich 15 minutes of this hard labour between 15 minutes of running at a relaxed pace, then you'll soon be running faster with less exertion.

3. Reach Enlightenment
This one starts simply: "Say hi and thank you as frequently as possible". Engaging with others and showing gratitude helps flesh out the characteristics in your world and makes it a richer, friendly place. This eases you out of the attack mode you busy life may seem to require.

4. Leave Stress at the Office
Establish one routine for day's star and end. When you start work in the morning, the routine can be: coffee/tea, read email and check today's to-do list. After you finish your last task of the day, make a plan for tomorrow and start your ritual to signal the end of office hours. Do something you find enjoyable and relaxing. For example, listen to a specific singer or band every day on your commute home, or work out for 30 minutes after you arrive home or drink a glass of wine at 7 p.m. each night.

The fate of Adobe Flash

The war between Adobe and Apple still continues. Apple blocks Flash in iPhone and iPad, and it results to some companies abandon Flash and use HTML5 instead. According to the current situation, in order to

Fast Reading Method

a good Blog article about fast reading: http://roman-rytov.typepad.com/miles/2006/11/how_to_read_fas.html

Solve USB Problem in VirtualBox (Fedora)

1. create a group "vboxusers" and make user your current user is in the group "vboxusers"

2. check the group id of "vboxusers", for example, 501

3. Add the following line at the end of /etc/fstab:

none /sys/bus/usb/drivers usbfs devgid=501,devmode=664 0 0

4. reboot

5. start VirtualBox

USB Application Programming in Windows

1. MSDN - USB device driver
http://msdn.microsoft.com/en-us/library/ms790518.aspx

2. USB Windows Library
http://libusb-win32.sourceforge.net/#documentation

3. AVR USB Software Packages
http://www.atmel.com/dyn/products/tools_card.asp?tool_id=4199

4. Easy HID package
http://www.protongeeks.com/index.php?option=com_content&task=view&id=136&Itemid=30