kilabit.info
Simple | Small | Stable | Secure

Mergesort rulez!

Analysis of Sorting Algorithm for Large Data

Comparing several sorting algorithm to measure the most efficient algorithm (in processing time and and speed) for sorting large data, data where their size is larger than system memory.

Sorting algorithms that I use in this analysis:

  • Merge sort

  • Bucket sort

  • Quick sort

  • Binary sort

Test Machine,

  • cpu: Intel(R) Celeron(R) CPU 550 @ 2.00GHz

  • cache size: 1024 KB

  • RAM size: 512 MB

  • OS: openSUSE 10.3 (default install)

Some notes:

  • Time's includes read/write of data.

  • Input and output data is in csv file format, with 11 columns.

Test 1 Sorting Random Data

                           +-----------------------------------------------------+
                           | Size of Input Data (* 1,000,000 of record)          |
        +------------------+-----------------------------------------------------+
        |  Sort Algorithm  |   2.5    |    5    |    10    |    15    |    20    |
+-------+------------------+----------+---------+----------+----------+----------+
|       | Merge sort       |   59.37  |  126.16 |  265.05  |  421.84  |  586.44  |
| Times | Binary sort      |   66.58  |  145.03 |  299.72  |  464.23  |  662.62  |
| (sec.)| Bucket sort      |   77.98  |  159.7  |  353.45  |  586.06  |  835.25  |
|       | Quick sort       |   63.31  |  133.99 | 1475.81  | 1858,22  | 2036.56  |
+-------+------------------+----------+---------+----------+----------+----------+
Comparison
of sorting algorithm with random data

Test 2 Sorting Ascending Data (data that already sorted)

                           +-----------------------------------------------------+
                           | Size of Input Data (* per 1,000,000 of record)      |
        +------------------+-----------------------------------------------------+
        |  Sort Algorithm  |   2.5    |    5    |    10    |    15    |    20    |
+-------+------------------+----------+---------+----------+----------+----------+
|       | Merge sort       |   43.88  |   86.62 |  175.64  |  263.99  |   355.99 |
| Times | Binary sort      |   50.48  |  100.53 |  203.17  |  308.55  |   408.77 |
| (sec.)| Bucket sort      |   64.69  |  129.63 |  256.31  |  390.55  |   501.11 |
|       | Quick sort       |   67.83  |  149.57 | 1839.96  | 9582.04  | 10667.31 |
+-------+------------------+----------+---------+----------+----------+----------+
Sort
comparison ascending order

Test 3: Sorting Descending Data

This benchmark sort data that already sorted in reverse order.

                           +-----------------------------------------------------+
                           | Size of Input Data (* 1,000,000 of record)          |
        +------------------+-----------------------------------------------------+
        |  Sort Algorithm  |   2.5    |    5    |    10    |    15    |    20    |
+-------+------------------+----------+---------+----------+----------+----------+
|       | Merge sort       |   44.77  |  89.42  |  177.28  |   275.61 |   366.61 |
| Times | Binary sort      |   50.81  | 100.59  |  202.02  |   307.47 |   405.98 |
| (sec.)| Bucket sort      |   67.83  | 127.37  |  256.24  |   384.67 |   513.96 |
|       | Quick sort       |   68.97  | 151.07  | 6572.53  | 13161.53 | 10335.81 |
+-------+------------------+----------+---------+----------+----------+----------+
Comparison
of sorting algorithm with descended data