Java VM 1.6.0 Sorting Collections

I have been having some trouble with the performance of Java. In my
code I have narrowed it down to the sort:

For instance:

import java.util.*;
public class SortTest
{
   public static void main(String args[])
   {
      final int vecSize = 1000000;
      ArrayList<Double> vec = new ArrayList<Double>(vecSize);
      final int numItr = 10;
      ArrayList<Double> times = new ArrayList<Double>(numItr);
      for (int i=0; i<numItr; ++i)
      {
         for (int k=0; k<vecSize; ++k)
         {
             vec.add(k,Math.random());
         }
         long startTime = System.nanoTime();
         java.util.Collections.sort(vec);
         long endTime = System.nanoTime();
         times.add(i,(endTime-startTime)*1.e-9);
         vec = new ArrayList<Double>(vecSize);
      }
      double avg=0.0;
      for (Double val:times)
      {
         avg += val;
      }
      avg /= times.size();
      System.out.println("To sort " + vec.size() + " elements " +
         numItr + " times took " + avg + " seconds on average");

   }
}

This prints about 0.58 seconds on average. How can I optimize this
reasonably? Note I am only timing the sort function. Using an array
instead of ArrayList is not an option. I tried Vector but it didn't
help. The equivalent C++ code (using vector) runs in about 0.37
seconds when built with optimization (g++ version 4.2.1 using -03
optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7
with 4 GB of ram. I also tried this example on Linux and saw no
difference. What is causing over 40% difference in speed? I must be
doing something wrong in my java code.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <sys/time.h>
#include <numeric>
using namespace std;

template <class T>
void FillRand(T start, T end)
{
   while (start != end)
   {
      *start++ = double(rand())/RAND_MAX;
   }
}

class TimeStamp
{
public:
        void start()
        {
                gettimeofday(&st_val,0);
        }
        void stop()
        {
                gettimeofday(&end_val,0);
        }
        double elapsedSec() const
        {
                return end_val.tv_sec-st_val.tv_sec +
                (end_val.tv_usec-st_val.tv_usec)*1.e-6;
        }
private:
        timeval st_val;
        timeval end_val;
};

int main()
{
   vector<double> vec(1000000);
   const long num_itr = 10;
   vector<double> time_stamps(num_itr);
   TimeStamp ts;
   for (long i=0; i<num_itr; ++i)
   {
      FillRand(vec.begin(),vec.end());
      ts.start();
      std::sort(vec.begin(),vec.end());
      ts.stop();
      time_stamps[i] = ts.elapsedSec();
   }
   double avg=std::accumulate(time_stamps.begin(),time_stamps.end(),
0.0)/time_stamps.size();
   cout << "To sort " << vec.size() << " elements took " << avg << "
seconds on average\n";
}