Implementation of quicksort seems to be taking more time than Mergesort
After trying lots of things to find out where the issue was, I changed the function that created the random array, and it turns out QuickSort actually works faster now. I don't really know why, but it seems that the way I created the array adversely affected the performance of QuickSort. Now, what I did was that instead of generating an array of random integers, I generated an array form 1 to n and then shuffled it, as follows:
public static int[] permutation(int n) { int[] a = new int[n]; for (int i = 0; i < n; ++i) a[i] = i + 1; for (int i = 0; i < n; i++) { int r = i + rnd.nextInt(n - i), tmp = a[i]; a[i] = a[r]; a[r] = tmp; } return a;}