diff --git a/playlistitem.h b/playlistitem.h
--- a/playlistitem.h
+++ b/playlistitem.h
@@ -179,9 +179,11 @@
     //virtual void paintCell(QPainter *p, const QColorGroup &cg, int column, int width, int align);
     //virtual void paintFocus(QPainter *, const QColorGroup &, const QRect &) {}
 
-    virtual int compare(QTreeWidgetItem *item, int column, bool ascending) const;
+    virtual int compare(const QTreeWidgetItem *item, int column, bool ascending) const;
     int compare(const PlaylistItem *firstItem, const PlaylistItem *secondItem, int column, bool ascending) const;
 
+    bool operator<(const QTreeWidgetItem &other) const;
+
     bool isValid() const;
 
     void setTrackId(quint32 id);
diff --git a/playlistitem.cpp b/playlistitem.cpp
--- a/playlistitem.cpp
+++ b/playlistitem.cpp
@@ -19,9 +19,11 @@
 #include <config-juk.h>
 #include <kiconloader.h>
 
-#include <QPixmap>
+#include <QCollator>
 #include <QFileInfo>
+#include <QHeaderView>
 #include <QGlobalStatic>
+#include <QPixmap>
 
 #include "collectionlist.h"
 #include "musicbrainzquery.h"
@@ -43,6 +45,14 @@
 #endif
 }
 
+static int naturalCompare(const QString &first, const QString &second)
+{
+    static QCollator collator;
+    collator.setNumericMode(true);
+    collator.setCaseSensitivity(Qt::CaseInsensitive);
+    return collator.compare(first, second);
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 // PlaylistItem public methods
 ////////////////////////////////////////////////////////////////////////////////
@@ -292,16 +302,16 @@
     QTreeWidgetItem::paintCell(p, colorGroup, column, width, align);
 }*/
 
-int PlaylistItem::compare(QTreeWidgetItem *item, int column, bool ascending) const
+int PlaylistItem::compare(const QTreeWidgetItem *item, int column, bool ascending) const
 {
     // reimplemented from QListViewItem
 
     int offset = playlist()->columnOffset();
 
     if(!item)
         return 0;
 
-    PlaylistItem *playlistItem = static_cast<PlaylistItem *>(item);
+    const PlaylistItem *playlistItem = static_cast<const PlaylistItem *>(item);
 
     // The following statments first check to see if you can sort based on the
     // specified column.  If the values for the two PlaylistItems are the same
@@ -337,9 +347,9 @@
         return 0;
 
     if(column < offset) {
-        QString first = firstItem->text(column).toLower();
-        QString second = secondItem->text(column).toLower();
-        return first.localeAwareCompare(second);
+        QString first = firstItem->text(column);
+        QString second = secondItem->text(column);
+        return naturalCompare(first, second);
     }
 
     switch(column - offset) {
@@ -376,11 +386,17 @@
             return 1;
         break;
     default:
-        return QString::localeAwareCompare(firstItem->d->metadata[column - offset],
-                                           secondItem->d->metadata[column - offset]);
+        return naturalCompare(firstItem->d->metadata[column - offset],
+                              secondItem->d->metadata[column - offset]);
     }
 }
 
+bool PlaylistItem::operator<(const QTreeWidgetItem &other) const
+{
+    bool ascending = playlist()->header()->sortIndicatorOrder() == Qt::AscendingOrder;
+    return compare(&other, playlist()->sortColumn(), ascending) == -1;
+}
+
 bool PlaylistItem::isValid() const
 {
     return bool(d->fileHandle.tag());