So basically i have an array of size 10^7 and i'm supposed to use an insert sort on the array. The sort works for smaller arrays, (all the way up to 10^5) but any bigger and nothing seems to work could anybody help me out?

This is my insert sort let me know if you need any other info!

public static void insertSort(int[] arr){

int x, y;
for(y=1; y< arr.length; y++) {
int temp = arr[y];
x = y;
while(x>0 && arr[x-1] >= temp){
arr[x] = arr[x-1];
--x;
}
arr[x] = temp;
}
}

Insertion Sort has an average case O(n^2) runtime. This means if your array is 10^7 you are doing 10^14 comparisons. That is 100,000,000,000,000 comparisons. If you're computer has a 3GHz, it can do 3 billion mathematical operations a second. That means it would take (100000/3) seconds to complete all comparisons in the average case. That is a little over 9 hours. Even if you had a 5GHz processor it would still take almost 6 hours to complete.

Your professor wants you to be able to do an insertion sort on a 10^7 sized array? I highly doubt that. If he did, drop the course as he is a fucking moron. Insertion sorts algorithm isn't dependant on the size of the array. It will sort a 100 element array just as well as a 100000000 element array. The only trade off is time. And if he really wants you to sort a 10^7 array then he expects you to waste 9 hours letting it run so it can complete the sort.

I actually just did those calculations as well and emailed the TA, turns out there was a revised version put out the other day that states to use 10^5 instead of 10^7! Everything seems to work now!

10^5 would be significantly less of a time sink. By dropping the order of magnitude by 2 you effectively change the run-time from 9 hours to 3 seconds. Still, it is weird that he is requiring you to use such a large array.

I still stand by my original statement. Any professor that would have you implement an O(n^2) sorting algorithm and then require it to be able to sort an array of a specific size doesn't understand the very algorithm he asked you to implement. What the fuck is the point of that? The algorithm isn't going to suddenly fail just because you asked it to sort too much stuff. It's just going to take an extremely long time to do it. There is no difference in the algorithm to sort 10^5 than 10^7. Sure you can do some optimizations for the best case scenario, but it isn't going to affect the average run-time. There should be another professor teaching this course as well. I recommend switching to his/hers. My experience with professors like this tells me you will not learn what you should from him and because of this your GPA will suffer.

my guess is they are implementing various sorting algorithms and then looking at the run time. and the prof wanted to show that different sorting algorithms can have drastically different run times. Then wanted them to try it on large size array so they can actually see the differences. i.e. if you do all the different sorts with n=50 you won't really be able to see any difference in time

You can do that simply by plugging in the array size to N^2 of O(N^2). You don't tell a bunch of freshmen that your implementation must work for 10^7 sized array. Because before you talk about run-time analysis of comparison based sorting algorithms, all they will think is "shit I ran the program and it froze...I must have messed up the implementation." So you end up having issues like what OP is having. His algorithm is a fine insertion sort, but he is too hung up on making it work for 10^7 because he hasn't been taught anything about the run-time of O(n^2) algorithms. This was a shitty assignment.

The correct way to do this would be to have him implement insertion sort and then give him sample test data. Then have him implement bubble sort, selection sort. Then have him implement mergesort or quicksort. Then after you have gone through all of those tell him to run each with new sample data. This time the data has the 10^7 array. Now he gets to see each sorting algorithm handle that data. After he does that he is to answer one question: Explain why quicksort and mergesort were able to sort this data but insertion and selection sort took ages. By then, in lecture, the professor would have already gone over each algorithm and explained its run-time and what it means. Now the student is equipped to handle this concept.

Do you see the difference?

Make sure no one lets you near code efficient applications.

Here is various sorting implantations I did in ruby a while back testing on an array of 1000 numbers (only 20 times the number you specified to show results) these results are the time required per sort (doing 10 sorts on a row on the same random data).


Saying you don't notice a difference between sorts is just retarded.

This post was edited by AbDuCt on Oct 1 2014 11:13pm

This is exactly what I am talking about. You can do run-time analysis without scaring your students into thinking they did something wrong by requiring that their sorting algorithm "work" with an astronomically high set of data. You can teach the same concept with data orders of magnitude lower than that.