Register

Which sorting algorithm can be used to sort a random linked list with minimum time complexity ?

14,511 views
1 votes
1 votes
Which sorting algorithm can be used to sort a random linked list with minimum time complexity ?

A)mergesort

B)quicksort

C)radixsort

D)insertionsort

E)heapsort
User Avatar

3 Answers

1 votes
1 votes

Merge Sort can be used for sorting Linked List and It will take O(nlogn).

We'll not prefer others :

1. Insertion Sort: takes O(n^2) . But we need Smaller TC.
2. QuickSort: Can't Be implemented Using LinkedList Because Indexing is Involved in Quicksort. But no indexing is present in LinkedList.
3. HeapSort: It requires The element of the linked list to be stored in an array , SInce HeapSort can only be implemented on an array Easily.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

8 votes
8 votes
2 answers
1
radha gogia asked Jul 19, 2015
20,217 views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)(B) Heap Sort with time complexity O(nLogk)(C) Quick Sort with time complexity O(kLogk)(D) Merge Sort with time complexity O(...
User Avatar
6 votes
6 votes
2 answers
3
radha gogia asked Jul 15, 2015
9,037 views
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true?
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true? 1. Insertion sort will...
User Avatar
1 votes
1 votes
1 answer
4
Purple asked Jan 27, 2016
24,713 views
If the number of records to be sorted is small, then which sorting can is efficient?
If the number of records to be sorted is small, then ...... sorting can be efficient. A. Merge B. Heap C. Insertion D. Bubble
If the number of records to be sorted is small, then ...... sorting can be efficient.A. MergeB. HeapC. InsertionD. Bubble
User Avatar
Link Copied!