Not going to talk a lot here, but I wanted to share 2 quick things. If you are not using Cloudflare…..use it. It’s a CDN, but also so much more. It can protect your site from attacks and has a handy firewall, also a handy interface to handle your DNS, some nifty analytics, and can also handle your SSL cert to make it dead simple to go https. One of my favorite things is the speed optimizations where it can automatically minify your CSS and JS as well as do some very cool image optimization. Best of all it’s free for small companies and cheap for large….I use it on all my work sites and when I get some time I’m switching this site to it. They’ve also just implemented a new geocentric load balancer that I’m excited to try.

The other things I wanted to mention was this site HTACCESS Tester. If you’ve ever had to deal with an htaccess file, and who hasn’t if you’re doing serious web dev for SEO, you know it’s a pain in the ass….it can do remarkable things w/url rewrites and 301’s, BUT it can be incredibly evil as well. You probably already know about the tag you can insert into your virtual host configuration to turn on logging for htaccess (LogLevel alert rewrite:trace6), but that log is waaaay too much info, especially with a large .htaccess file. Enter htaccess tester. Now you can write a rule and check if it gets applied the way you think it will…seriously, it’s a life saver.

# Author Archives: stanquinn

# Dual Pivot Quicksort Kicks Butt!

So while I was checking out different flavors of quicksort after taking the Coursera Algorithms class I found out about a new version of quicksort that was much faster then I had anticipated. Java 7 had recently modified their sort function to use a new algorithm called Dual Pivot Quicksort, so I thought I’d check it out. I found a java version and recoded it to be javascript. It works well, but currently only sorts integers and in ascending order. Ideally I should modify it to work the same way the normal array sort algorithm works, that way I’d be comparing apples to apples. I believe under the hood that the V8 javascript engine has upgraded to the new dual pivot algorithm, but it does have some additional checks and improved functionality where you can pass in the sorting algorithm, which may be why it’s consistently slower then my javascript version of dual pivot quicksort that I coded up. It’s consistently 10%-50% faster then the default array.sort() algorithm. The default sort is going to work well enough for 90% of your sorting cases, but if you are following the 10/90 rule and have narrowed down the bottleneck in your code and want to optimize sort, then I would advise taking this code and modifying it for your needs since it will always be faster then the default array.sort(). Check it out on JSPerf http://jsperf.com/javascript-quicksort-comparisons

Technically JS Perf says it’s ±10.25% faster then the default sort the last time I ran it, but it does vary quite a bit. My guess is that it probably varies based on how random the shuffle is. I suppose it could be because we are comparing a lion to a cheetah….the default sort sorts any object, and lets you pass in the sorting function, while the dual pivot quicksort I coded up only works on integers and in ascending order, but I’d still say it’s worth looking into, ESPECIALLY if whatever language you are coding in hasn’t rewritten their quicksort to use the new algorithm. I made it a single variable module, and you call it with **DualPivotQuicksort.sort(arr)**. Here’s the code.

```
/******** Dual Pivot QuickSort ***************/
var DualPivotQuicksort = (function() {
var dualPivotQS = {};
dualPivotQS.sort = function(arr, fromIndex, toIndex) {
if(fromIndex === undefined && toIndex === undefined){
this.sort(arr, 0, arr.length);
} else{
rangeCheck(arr.length, fromIndex, toIndex);
dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
}
return arr;
}
function rangeCheck(length, fromIndex, toIndex) {
if (fromIndex > toIndex) {
console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
console.error(fromIndex);
}
if (toIndex > length) {
console.error(toIndex);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function dualPivotQuicksort( arr, left, right, div) {
var len = right - left;
if (len < 27) { // insertion sort for tiny array
for (var i = left + 1; i <= right; i++) {
for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
return;
}
var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest
// "medians"
var m1 = left + third;
var m2 = right - third;
if (m1 <= left) {
m1 = left + 1;
}
if (m2 >= right) {
m2 = right - 1;
}
if (arr[m1] < arr[m2]) {
swap(arr, m1, left);
swap(arr, m2, right);
}
else {
swap(arr, m1, right);
swap(arr, m2, left);
}
// pivots
var pivot1 = arr[left];
var pivot2 = arr[right];
// pointers
var less = left + 1;
var great = right - 1;
// sorting
for (var k = less; k <= great; k++) {
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
else if (arr[k] > pivot2) {
while (k < great && arr[great] > pivot2) {
great--;
}
swap(arr, k, great--);
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
}
}
// swaps
var dist = great - less;
if (dist < 13) {
div++;
}
swap(arr, less - 1, left);
swap(arr, great + 1, right);
// subarrays
dualPivotQuicksort(arr, left, less - 2, div);
dualPivotQuicksort(arr, great + 2, right, div);
// equal elements
if (dist > len - 13 && pivot1 != pivot2) {
for (var k = less; k <= great; k++) {
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
else if (arr[k] == pivot2) {
swap(arr, k, great--);
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
}
}
}
// subarray
if (pivot1 < pivot2) {
dualPivotQuicksort(arr, less, great, div);
}
}
return dualPivotQS;
}());
/************************************************/
```