Choose the Fastest Sort Part II

Computer Science Level 1

To sort the list

A = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] , A = [0,1,2,3,4,5,6,7],

which algorithm is faster?

Mergesort Insertion Sort Quicksort

Karleigh Moore by Karleigh Moore , 27, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Karleigh Moore
Mar 23, 2016

Since this array is already in sorted order, Insertion Sort takes O ( n ) O(n) time. Mergesort takes O ( n lg ⁡ n ) O(n \lg n) no matter the state of the input, and Quicksort takes O ( n lg ⁡ n ) O(n \lg n) in its best case (when the input is already sorted).

9 Helpful 0 Interesting 0 Brilliant 0 Confused

The quicksort takes O(nlgn) only when input is random and takes the form of O(n^2) when the input is already sorted. Please check into it.

Puneet Pinku - 1 year, 3 months ago

Yes, you are right :). The quicksort takes O(n^2) when the array is already sorted, which makes it the worst-case scenario.

A Former Brilliant Member - 3 months, 1 week ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...