Category: Algorithms

JavaScript Mergesort: Top-Down vs Bottom-Up

In my continuing series on JavaScript algorithms, I thought it might be fun to examine two methods for implementing “mergesort”.

Mergesort is essentially a “divide and conquer” technique, where the algorithm breaks an array into smaller pieces. Each of the small pieces is sorted and then recursively merged back together.

Mergesort is an attractive option for sorting large arrays because it is fast… and we’ll look at its efficiency in a moment. However, it also has a disadvantage: the algorithm requires more memory than Selection Sort and Insertion Sort, so for systems in which memory usage must be kept low mergesort may not be a good option.

Pong: Built with Sencha Touch

How many of you played Pong when you were little? I’m old enough to remember playing it in the arcade and on my Atari 2600. I’m such a nerd that I decided to recreate Pong using Sencha Touch!

I did some searching on the interwebs to find the original Pong AI algorithm… but it seems like everyone and their mother has a different take on it. I’d love to hear your thoughts. How can I improve this game?

Book Review: Algorithms, 4th Edition

When I was in college I had the (dis)pleasure of taking a graduate-level class on algorithms. Although I loved the content, I did not have enough practical experience to make the most of the material.

That’s why I was really excited when Pearson Education offered me the chance to review Algorithms, 4th Edition. In the eight years since I took that class I’ve learned a lot about software engineering… this would be a great opportunity to see if I had learned as much as I thought!

JavaScript: Selection vs. Insertion Sort

“Selection Sort” and “Insertion Sort” are two popular sorting algorithms. If they have the same Big-O notation, which is better?

The point here is that Big-O notation, although certainly helpful, doesn’t always tell us the full story. It’s great to know what the worst possible performance is for our code… but we need to know how often to expect that situation.

JavaScript: Binary Search vs Linear Search

The linear search algorithm is often “good enough” for most applications. Although optimization would improve performance, the benefit might only be minimal if our data set (stored in an array) is relatively small.

But what happens to our algorithm as the data set increases in size?

I put together a short example comparing the expected (worst-case) and actual performance of these two search algorithms.