The running time of Sort1 on an almost sorted array of size n is quadratic, the running time of Sort2 on an almost sorted array of size n is propotional to n, although it's very small. When comparing Problem 2 result with Problem 3 result, the running time of Sort1 on a random array of size n is ½ of that of Sort1 on an almost sorted array of size n, which means Sort1 is very inefficient for an almost sorted array because it ignores that fact that no element in an almost sorted array is more than a "distance" 10 from its position in a sorted list. Sort2 takes advantage of this observation and is thus much, much faster. The original data is listed below. Testing Problem 3... n = 1000: Sort1 time = 0.039, Sort2 time = 0.001 n = 2000: Sort1 time = 0.1503, Sort2 time = 0.001 n = 3000: Sort1 time = 0.3213, Sort2 time = 0.0081 n = 4000: Sort1 time = 0.5829, Sort2 time = 0.002 n = 5000: Sort1 time = 0.9103, Sort2 time = 0.003 n = 6000: Sort1 time = 1.3069, Sort2 time = 0.007 n = 7000: Sort1 time = 1.7856, Sort2 time = 0.008 n = 8000: Sort1 time = 2.3313, Sort2 time = 0.007 n = 9000: Sort1 time = 2.9553, Sort2 time = 0.01 n = 10000: Sort1 time = 3.7524, Sort2 time = 0.011