The running time of both Sort1 and Sort2 functions on an random integer array of size n is quadratic.

Sort2 is almost twice as fast as Sort1.

Sort2 is more efficient than Sort1 due to the following reason. Each time a new number is inserted, for Sort1,  the list must be traversed from the very beginning; for Sort2, the list can be traversed forward or backward from the current position, which saves time. 

The original data is listed below.

Testing Problem 2...
n = 1000: Sort1 time = 0.0191, Sort2 time = 0.011
n = 2000: Sort1 time = 0.073, Sort2 time = 0.0411
n = 3000: Sort1 time = 0.1672, Sort2 time = 0.0872
n = 4000: Sort1 time = 0.2975, Sort2 time = 0.1591
n = 5000: Sort1 time = 0.4633, Sort2 time = 0.2488
n = 6000: Sort1 time = 0.672, Sort2 time = 0.3585
n = 7000: Sort1 time = 0.908, Sort2 time = 0.49
n = 8000: Sort1 time = 1.1917, Sort2 time = 0.6449
n = 9000: Sort1 time = 1.5013, Sort2 time = 0.814
n = 10000: Sort1 time = 1.8656, Sort2 time = 1.018