How to plot algorithm runtime for huge input set? Fo my bachelor thesis, I want to compare the runtime of two algorithms. The runtime is measured by letting these algorithms run for every value in a huge input set. This input set can be partitioned into three subsets $X_1$, $X_2$, $X_3$. Each subset contains 40,000 values, the algorithms are executed once for each value. In my plot I want to have the input sets on the x-axis, and each set's runtime on the y-axis. What would be a good representation for this kind of data?
I first tried a scatter plot, but because a few values are really far outliers, the scale of the plot squashes most important values into visually indistinguishable areas. I then superimposed the lines for the mean value, with error bars for the standard deviation:

This clearly demonstrated how far and few these outliers were. The non-outlier scatter values are not even recognizable under the mean value lines, which themselves aren't very distinguishable. Because these outliers are not really important for my evaluation, I decided to change my graph to only show mean values with standard deviation:

These partly improve the situation, but to fit the standard deviation onto the plot, the mean values are still somewhat close. But I feel removing the error bars would be neither true to the data nor scientifically accurate.
Additionally plotting the data like this makes the errors bars go below zero, which indicates a bad representation of the data, since time values below zero are obviously impossible.
How can data like this be represented better? Is showing the mean value actually a good idea in this case? Or would other characteristics like the median be better? Or even remove the say 5% from that data, that constitute the furthers outliers?
Further I have no idea what a good format for the error bars would be that would avoid the case of them going below zero. Is there something like the standard deviation above the mean value and one below that i could then plot asymmetrically?
I am both looking for insight into this particular case and resources on how to showcase data in general.
In case anyone wants to try my themselves at it, I made the first 100 values of each data point available (the above graphs were made with these): http://pastebin.com/sjdPy8Np
 A: Continuing the comment theme, you should find an explanation for your outliers to know whether to include them or segregate them. I notice that the outliers are oddly clumped. An outlier for one input set row seems to often go along with an outlier for the same row in another input set.

Regarding your graph, once you've worked out the outliers issue, box plots may be a viable option. Here's a version with outliers, but using a log transform (which may be appropriate if there is a multiplicative aspect to the algorithm).

That loses the within-row correlations. To emphasize those you could use the same marker symbol for values in the same row (until you run out of symbols!). Another approach is to a parallel coordinates plot, where every row is represented by a connected line.

Finally, don't feel obligated to summarize all your findings in a single plot.
Btw, if you post more data, please use a computer-friendly format like CSV or JSON.
A: The minimum values for each input set might be the most informative. A lot of nuisance factors can slow down your benchmark, but very few can cause the code to run faster The docs for the python benchmarking module timeit say:

It’s tempting to calculate mean and standard deviation from the result vector and report these. However, this is not very useful. In a typical case, the lowest value gives a lower bound for how fast your machine can run the given code snippet; higher values in the result vector are typically not caused by variability in Python’s speed, but by other processes interfering with your timing accuracy. So the min() of the result is probably the only number you should be interested in. After that, you should look at the entire vector and apply common sense rather than statistics.

You could then turn to extreme value theory to get a more rigorous estimate of the fastest that your code can possibly run. This, however, assumes that your code and data are fixed. In other words, you'd repeat this process for $X_1, X_2 \text{ and } X_3$, and then try to do some inference on the results (e.g., compare credible intervals or something).
As an alternative, I like @xan's suggestion of plotting on a log scale. Given the domain, it might be more appropriate to use $\log_2$ instead of $\log_{10}$--each increment then corresponds to doubling the running time and might match up with some theoretical analysis of your algorithm.  
A: I have a strong suspicion that your raw data are not normally distributed, given that your data are right-skewed and they cannot possibly be skewed left (bounded by zero). As you mentioned, assuming normality here results in error estimates which extend below zero, which I believe is inappropriate. You may want to consider possible transformations of your raw data. There is a good CV post here and a SixSigma page here that may help you begin to thoughtfully consider these alternate approaches.
The question about representing data may resolve itself a bit more once your data meet your assumptions about, for example, normality.
Good luck!
A: For my part, I would find the following most intuitive and illustrative: A stack of three plots, each corresponding to a subset, showing estimated density curves of both algorithms. (Example below, but note that they're simple pdfs, rather than estimated curves.)
To add more detail, you could include vertical lines demarcating your quantiles of choice. (Median, deciles, etc.)

