A Software Engineering Space

Rotate, Reverse, Block Swap, Repeat.

I was reading through a paper about block merge sort and in the article was a list of helper functions that the algorithm utilizes during its execution. This list was kind of a “who’s who” of array manipulation algorithms. These algorithms are useful for a whole lot more than just block merge sort, and so […]

Lets Talk Selection

Often times when we have a collection of values, we are more interested in the order statistics of the collection: find the min value, find the max value, find the K’th smallest value, and what have you. There are a number of data structures that efficiently support these operations: a binary search tree can support find […]

Another look at heapifying

Heaps are ubiquitous in computer science. If you need the minimum, or maximum of a collection, few choices are better than a heap for getting them. Heap-forming algorithms are the foundation of many different algorithms and data structures. From heapsort to priority queues, to huffman coding, heaps really are everywhere. Heaps make use of two […]

Shellsort: A Sorting Enigma

For the first 15 years or so of computing if you wanted an in-place general purpose sorting algorithm you were stuck with O(n^2) sorting algorithms. Insertion sort, selection sort, and bubble sort were about as far as the art of sorting had gotten at the time. That’s not to say faster sorting methods were not […]

Range Searching

Searching and sorting are the two most common processes performed on a computer, and for that reason a lot of research has gone into the various methods of performing those tasks. Range searching is an expansion of general searching, where instead of searching a collection for a specific element, you are interested in all of […]

Simplifying Mergesort

Mergesort is a beautiful algorithm. I make no secret of it being my favorite sorting algorithm (everybody has one of those, right?) and so I like to spend time playing around with it, thinking of different ways of implementing the concept. In this post I want to discuss a method of simplifying the merge sort […]