Time Comparison of Quick Sort, Insertion Sort and Bubble Sort

Comparing different sorting algorithms for time performance has always been amusing. It has been done tons of time. But you should try it out for yourself. Apart from fun, this comparison is very useful in real life. Companies and organisations need to sort and search data all the time. Thus it makes sense to compare and find the best suitable sorting method.

First let me show you the result in a neat graph (using MS Excel charts), displaying time (on y-axis) v/s list size (on x-axis).


If you are done analysing the graph, please note following points

  • The x-axis represents the number of elements sorted.
  • The x-axis is not linear (nor logarithmic). Its random, you see 1,000 then 5,000 then 10,000 and so on up to 3,00,000. The last three entries are linear however, and shows the highlight feature of the graph. The difference in the three algorithms performance.
  • Quick Sort seems to not want to let go off the axis. It is not a mistake, it is for real.
  • Bubble sort’s curve would make a dream come true graph for a company’s profit. Winking smile

Here I reproduce the result in tabular form –

Length Bubble Sort Insertion Sort Quick Sort
1000 0 0 0
5000 0.145 0.045 0
10000 0.6 0.18 0
50000 14.05 4.25 0.01
100000 56.9 17.62 0.02
200000 229.44 69.12 0.05
300000 513.34 154.22 0.065

Variations in numbers (time recorded)

Consider Insertion Sort’s time taken for 5000 integers, 0.045 seconds. This is an average value. Due to other processes going on at the same time as comparison, the recorded time varies during each run. It also varies from computer to computer (mine one is a decent one though, Intel i3 with 4 GB of RAM). Like in one execution, above time was recorded as 0.04 sec and in other it was 0.05 sec. Same goes for all the time values. In effect I have averaged the time taken in the 4 executions. For greater accuracy keep the number of samples to a minimum 10 (although I leave it to you). And also the code should be executed on a variety of computers and Operating Systems (again I leave that for you). However the differences are so pronounced that a variation of 5-10% does not affect the end result.

The big question?

You must wonder why I chose the above three algorithms for comparison. Why not merge sort (arguably the fastest sorting algorithm), or heap sort? And pray, why include Bubble Sort at all??

For one the beginners should know that their favourite sorting (Bubble sort), is umm, well, pathetic and un-acceptable. Second, that quick sort is indeed quick. And I had to take some medium performing algorithm, so Insertion Sort was chosen. All three of them are quite popular and easy to understand.

Give me the code

Yeah sure, here it is:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

long length = 1000;
const long max_length = 300000;

int list[max_length];

void read()
    ifstream fin("random.dat", ios::binary);
    for (long i = 0; i < length; i++)
        fin.read((char*)&list[i], sizeof(int));

void bubbleSort()
    int temp;
    for(long i = 0; i < length; i++)
        for(long j = 0; j < length-i-1; j++)
            if (list[j] > list[j+1])
                temp        = list[j];
                list[j]     = list[j+1];
                list[j+1]   = temp;

void insertionSort()
    int temp;
    for(long i = 1; i < length; i++)
        temp = list[i];
        long j;
        for(j = i-1; j >= 0 && list[j] > temp; j--)
            list[j+1] = list[j];
        list[j+1] = temp;

long partition(long left, long right)
    int pivot_element = list[left];
    int lb = left, ub = right;
    int temp;

    while (left < right)
        while(list[left] <= pivot_element)
        while(list[right] > pivot_element)
        if (left < right)
            temp        = list[left];
            list[left]  = list[right];
            list[right] = temp;
    list[lb] = list[right];
    list[right] = pivot_element;
    return right;

void quickSort(long left, long right)
    if (left < right)
        long pivot = partition(left, right);
        quickSort(left, pivot-1);
        quickSort(pivot+1, right);

int main()
    double t1, t2;

    for (length = 1000; length <= max_length; )
        cout << "\nLength\t: " << length << '\n';

        t1 = clock();
        t2 = clock();
        cout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";

        t1 = clock();
        t2 = clock();
        cout << "Insertion Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";

        t1 = clock();
        quickSort(0, length - 1);
        t2 = clock();
        cout << "Quick Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n";

        switch (length)
        case 1000 :
            length = 5000;
        case 5000 :
            length = 10000;
        case 10000 :
            length = 50000;
        case 50000 :
            length = 100000;
        case 100000 :
            length = 200000;
        case 200000 :
            length = 300000;
        case 300000 :
            length = 300001;

    return 0;

I encourage you to copy the code (modify it to suit your needs), compile it with your choice of compiler and execute it. And share the results with us. I will be glad to showcase here what you found (and how fast your computer runs Smile)

IMPORTANT : The above code requires a file ‘random.dat‘ which contains 3,00,000 integers stored randomly. This file is read each time before a sorting is performed. You can download it here http://www.box.net/shared/1n3r3hedv86351iun6f5 or here https://skydrive.live.com/?cid=a976bcd81e2434ba&sc=documents&id=A976BCD81E2434BA%21114# The file is 1.14MB sized.
Alternatively you can generate ‘random.dat‘ file through this code. This way you can generate a bigger file for more numbers.

#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

const size_t length = 300000;

int main()
    ofstream fout("random.dat", ios::binary);


    int r;
    for (size_t i = 0; i < length; i++)
        r = rand();
        fout.write((char*)&r, sizeof(r));

    return 0;

Also you can download both the codes, there executables and random.dat in this RAR file(1.01 MB) http://www.box.net/shared/31ofn1v53qrdm0y2cdce or here https://skydrive.live.com/?cid=a976bcd81e2434ba&sc=documents&uc=1&id=A976BCD81E2434BA%21116#

WARNING : The total execution time can exceed 20 minutes (or even more) on slow processors. It may seem that program is hung after sorting 50,000 numbers, but it is not so. The screen stops responding because, the bubble sort starts taking longer times (in several minutes). So nothing to worry, just watch a video or two on vimeo (or youtube).


I would conclude this, that

  • Bubble Sort is not suitable in any circumstance. It is an O(n2) algorithm with a large constant. In simple words, time required to perform bubble sort on ‘n’ numbers increases as square of ‘n’. Thus it is quite slow.
  • Insertion Sort is suitable for small files, but again it is an O(n2) algorithm, but with a small constant. Also note that it works best when the file(/numbers) is already almost sorted.
  • Quick Sort amazed me. Didn’t you get amazed?! Well it is an O(n*log(n)) algorithm on an average case and an O(n2) algorithm in the worst case scenario. (Quick sort’s worst case occurs when the numbers are already sorted!!) The graph speaks it all. You need this algorithm when the list is large and time is premium.

Have a nice time comparing!

This entry was posted in Algorithm, Programming and tagged , , , , , , . Bookmark the permalink.

30 Responses to Time Comparison of Quick Sort, Insertion Sort and Bubble Sort

  1. Hi, like your programme. But are you sure that quick sort sorts the WHOLE list properly? It seems like not.. maybe it should write the sorted file for comparison? Possibly some flaw in the techniques.. Just suggestion.

    Operating System
    MS Windows Vista Business 32-bit SP2
    Intel Core 2 Duo E8400 @ 3.00GHz 44 °C
    Wolfdale 45nm Technology
    4.00 GB Dual-Channel DDR2 @ 399MHz (6-6-6-18)
    Hewlett-Packard 2820h (XU1 PROCESSOR) 36 °C
    Hard Drives
    244GB Seagate ST3250310AS ATA Device (SATA) 33 °C

    I did not do anything while it was sorting. Processor was jumping 40-80%

    Length : 1000
    Bubble Sort : 0.004 sec
    Insertion Sort : 0.001 sec
    Quick Sort : 0.002 sec

    Length : 5000
    Bubble Sort : 0.117 sec
    Insertion Sort : 0.034 sec
    Quick Sort : 0.002 sec

    Length : 10000
    Bubble Sort : 0.471 sec
    Insertion Sort : 0.132 sec
    Quick Sort : 0.002 sec

    Length : 50000
    Bubble Sort : 11.846 sec
    Insertion Sort : 3.248 sec
    Quick Sort : 0.012 sec

    Length : 100000
    Bubble Sort : 47.114 sec
    Insertion Sort : 13.052 sec
    Quick Sort : 0.024 sec

    Length : 200000
    Bubble Sort : 189.192 sec
    Insertion Sort : 52.212 sec
    Quick Sort : 0.046 sec

    Length : 300000
    Bubble Sort : 437.146 sec
    Insertion Sort : 117.487 sec
    Quick Sort : 0.07 sec

    By these results- i really think there the quick sort can be incorrect.

  2. vinayakgarg says:

    @Peter : Thanks for sharing your results (in fact lots of details 🙂 ). Although i had printed a subset of sorted values after each sort. On your suggestion i actually added code to print the sorted result in a file. Although there are lot of values to check, I checked manually the output, and it is well Correct!. So I guess quick sort surprised you, didn’t it. 😀

  3. Sravan says:

    Can someone give the results of time comparison to execute these three algorithms for 1million random numbers. I tried it in java but my console is not showing all 1 million numbers on the screen.

    Also please let me know how we can calculate the exact time.. Can we have a timer inside the code that records the execution time? or do we have to calculate it manually?

    I would appreciate if i can have a java code to put up a timer inside the program for execution…so that the results would be accurate..

    Please help me..

    • vinayakgarg says:

      Console cannot show 1 million numbers. So instead of printing to console (like using System.out.println), print the numbers to a file, which you can read in a text editor. Or you can print to console only, but redirect the standard output to a text file.

      This is done by “java comparison > out.txt” while executing.

      I am not sure about timing in Java, but this should work->

      long start_time = System.nanoTime();
      long end_time = System.nanoTime();
      long duration = end_time - start_time;
  4. John says:

    I tried to add Merge sort to the comparison, but it didn’t work…can you show how to modify it, please?

  5. L says:

    sir, thanks for the article ! 🙂

  6. Thanks a lot for the code, but I have one suggestion.

    I was using your code to count the number of comparisons made by the quicksort and I believe I’ve found a mistake, that don’t compromise the sorting, but the efficiency.

    In the line 63, while(list[left] <= pivot_element), I had to add the comparison (left < right), leading to while( (left < right) && list[left] <= pivot_element). Without this comparison, during some runs the comparisons were being made between the pivot and an element outside the list limit. As I'm a beginner, a test with a 5-element list was very productive. 😉

    This means that, in the average, quicksort should be even faster.

    Best regards.


  7. shubhra singh says:

    Thanks 4 coding sir….I’m a new learner so can u provide me coding in c for comparison in complexity of quick, merge and bubble sort

  8. olatunde yusuf says:

    Thanks 4 coding sir, am very great-full …. plz can u provide me coding for comparison in complexity of insertion sort and merge sort only. am a new learner (answer in c++ plz)

  9. hitman4life says:

    Nice research work. I think it would be more interesting to compare quick sort with merge sort to check how 2 average time O(nlogn) do.

    Also is the data for the numbers generated randomly? How about different trends to fit in with insertion sort?

  10. YeahRight says:

    Was searching for valid comparison on the net and arrived on your page…
    Your test has a LOT of flaws.

    1/ What is your timer resolution ?
    2/ What kind of data do you use ? Random ? Nearly sorted ? Inversed ? Each of those impact hugely the outcome of the performance of the sort.
    3/ Load (or copy) the same data in memory like 100x time, so you wont include the loading time and then measure the TOTAL time for 100 sets ONCE.
    Then divide your total time by 100. You need to average the time for each run. There is no way your benchmark can be accurate given the current measurement system.

    Finding 0 for a quicksort of 5000 items, just doesn’t make any sense at all. It is most likely than the CPU takes at least a few 100k cycles. Most likely it takes probably around 0.1ms or 0.2ms for your sort.

  11. Shubham sharma says:

    Nice article Sir
    Sir i wanted to know how can we precisely calculate time in bubble sort and selection sort for 10 integers?

  12. JC says:

    Actually Bubble Sort is the fastest if the data set is already sorted. This actually occurs. If you maintain a data set and add a few records here and there, it is faster. If you don’t know anything about your data set you might want to use a mid-level performer. If you know that it is random, sure, quicksort is the best choice.

    • vinayakgarg says:

      No, Insertion sort is fastest for sorted data. Try running bubble sort on 1 Million sorted integers. And then insertion sort on the same data set.
      Bubble sort is always O(n^2). To see this notice the condition of both the `for` loops in bubble sort.
      Insertion sort however reduces to O(n) if the data is sorted. Check the loop condition for insertion sort in the code.

  13. Mariel Salem says:

    Sir is this possible is I have 6 number only? coz in out study we only have to sort 6 numbers…I always get 0 when I measure their time….. I really need to know 😦

  14. meer murtaza says:

    plz upload an other sorting articles

  15. Hi, I see that you are using the global variable “list” for storing and sorting the numbers. That way, once the bubblesort function is called, the array is already sorted. Naturally, when the insertion sort and quicksort are called after that, the functions are actually running on sorted data(that has been sorted by the bubblesort function).

    So for every loop in the main function, only bubblesort is actually sorting the input.

    Please check.

    • vinayakgarg says:

      Hi Ravina,
      Take a look at the loop in which sorting functions are called. Prior to invoking sort function, I have called “read();” function, which reads integers from a file containing random integers and adds it to “list”. So it is guaranteed that each sorting function has same input array.

  16. Levi says:

    Thank you for your code. It really helped me a lot. But I tried adding heap sort and merge sort but it doesn’t work. Do you know how it was done?

  17. Martin Dinev says:

    Is the quick sort result an april first’s joke?
    My results are for 1000: 1.453 , for 5000: 7.235, for 10000: 14.435, for the next one the program stopped and returned -1073741571 instead of 0… Help ASAP please

    • vinayakgarg says:

      This result is totally unexpected. Please verify if you are indeed running quick sort.

      • Levi says:

        I changed the array size to 3000 so the value for each case was:

        case 100 :
        length = 500;
        case 500 :
        length = 1000;
        case 1000 :
        length = 1500;
        case 1500 :
        length = 2000;
        case 2000 :
        length = 2500;
        case 2500 :
        length = 3000;
        case 3000 :
        length = 3001;

        And when I ran it, the quick sort’s time was 1000=0.384615, 1500=0.549451, 2000=0714286, 2500=0.879121, 3000=1.098901 and these times were larger than the bubble sort which isn’t supposed to. What could be the problem?

      • Martin Dinev says:

        I checked , but it ended up with another problem. I fixed it though 😀 So everything’s ok now and I hope you all have a nice day 🙂

    • Levi says:

      I would like to ask how did you fix the problem for the quick sort because I’m having the same problem. Thank you.

      • Martin Dinev says:

        Well seems that you need that file from which the numbers are read.. I didn’t read the whole article and just went with copy-pasting the code. I later solved the problem using rand() , srand(time(0)), and that way I allways got new items for sorting, I guess you could google those functions

      • Martin Dinev says:

        Oh, I just saw that actually even that is mentioned in the article.. So maybe you had the same problem?

    • Levi says:

      Yeah. I’m having the same problem. Can you show me the code, if you don’t mind sharing it? I really need to know how will it get fixed. Thank you.

  18. Michael says:

    Is anyone else getting a Segmentation fault for quick sort? i changed the lengths to 1………to a 1000000.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s