Sorting Algorithms

What is a sorting algorithm?

An algorithm that arranges elements of a list or array in a specific order (ascending or descending).

What are the main types of sorting algorithms?

Comparison-based and non-comparison-based sorting.

What are examples of comparison-based sorting algorithms?

Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort.

What are examples of non-comparison-based sorting algorithms?

Counting Sort, Radix Sort, Bucket Sort.

What is the average time complexity of Bubble Sort?

O(n²)

What is the average time complexity of Insertion Sort?

O(n²)

What is the average time complexity of Selection Sort?

O(n²)

What is the average time complexity of Merge Sort?

O(n log n)

What is the average time complexity of Quick Sort?

O(n log n)

What is the average time complexity of Heap Sort?

O(n log n)

What is the average time complexity of Counting Sort?

O(n + k), where k is the range of input.

What is the average time complexity of Radix Sort?

O(nk), where k is the number of digits.

What is the best-case time complexity of Insertion Sort?

O(n), when the input is already sorted.

Which sorting algorithm is best for nearly sorted data?

Insertion Sort

What is the worst-case time complexity of Quick Sort?

O(n²), when the pivot divides the array unevenly.

Which sorting algorithm uses divide and conquer?

Merge Sort and Quick Sort

Which sorting algorithm is stable and has O(n log n) time?

Merge Sort

What is a stable sorting algorithm?

An algorithm that maintains the relative order of equal elements.

Is Quick Sort a stable algorithm?

No

Is Merge Sort stable?

Yes

Is Heap Sort stable?

No

Is Counting Sort stable?

Yes

What is the space complexity of Merge Sort?

O(n), due to auxiliary array.

What is the space complexity of Quick Sort?

O(log n), for recursion stack.

What is the space complexity of Bubble Sort, Insertion Sort, and Selection Sort?

O(1), as they are in-place sorting algorithms.

What is the concept of divide and conquer?

Divide the problem into subproblems, solve them recursively, and combine the results.

Which algorithm builds a max-heap to sort elements?

Heap Sort

Which algorithm chooses a pivot element and partitions the array?

Quick Sort

What is the pivot in Quick Sort?

An element used to divide the array into parts smaller and greater than itself.

What is the main advantage of Quick Sort?

Faster in practice for large datasets and can be done in-place.

Which sorting algorithm repeatedly swaps adjacent elements if they are in the wrong order?

Bubble Sort

Which sorting algorithm selects the smallest element and places it at the front?

Selection Sort

Which algorithm inserts elements into their correct position one at a time?

Insertion Sort

What is a non-comparison-based sorting algorithm?

An algorithm that doesn’t compare elements but uses properties like digit or frequency.

Which sorting algorithm is efficient for small arrays?

Insertion Sort

Which algorithm performs well on large datasets with uniform distribution?

Radix Sort or Merge Sort

What is bucket sort?

A sorting technique that distributes elements into buckets and sorts them individually.

Is bucket sort stable?

It can be, if stable sort is used within buckets.

Which sorting algorithm is best for linked lists?

Merge Sort

Why is Quick Sort not ideal for linked lists?

Due to poor partitioning and random access issues in linked lists.

Which sorting algorithm has consistent O(n log n) performance?

Merge Sort and Heap Sort

Why is Counting Sort not suitable for large ranges?

Because it requires extra space proportional to the range of values.

Which sorting algorithms are commonly used in libraries?

Merge Sort, Quick Sort, TimSort (a hybrid of both).

What is TimSort?

A hybrid sorting algorithm based on Merge Sort and Insertion Sort, used in Java and Python standard libraries.

What is the difference between stable and unstable sort?

Stable keeps the order of equal elements; unstable may not.

Which algorithm is preferred when memory is limited?

Heap Sort, as it's in-place and doesn't need extra memory.

Why might Merge Sort be preferred over Quick Sort?

It is stable and guarantees O(n log n) time complexity.

Why might Quick Sort be preferred over Merge Sort?

It usually outperforms Merge Sort in practice due to in-place sorting and better cache usage.

What is shell sort?

An improved version of insertion sort using gaps to compare and move elements.

Is shell sort stable?

No

What is the best sorting algorithm for large, unsorted datasets in general?

Quick Sort or Merge Sort, depending on constraints.

What is the main drawback of Bubble Sort?

Very slow on large datasets due to O(n²) time.

What is the key idea behind Counting Sort?

Counting the number of occurrences of each unique value.

Is Radix Sort stable?

Yes, if the stable sort is used at each digit.

Does Radix Sort work with negative numbers?

Only if modified, otherwise it works with non-negative integers.

What kind of data is Radix Sort suitable for?

Fixed-length numeric or string keys.

How does Bucket Sort work?

Divides data into a fixed number of buckets, sorts each bucket, then combines them.

Which sorting algorithm is based on binary heap?

Heap Sort

What is heapify in Heap Sort?

The process of maintaining the heap property in a subtree.

What is the time complexity to build a heap?

O(n)

What is the complexity of heapify operation?

O(log n)

Which sorting algorithm is used in Java’s Arrays.sort() for primitives?

Dual-pivot Quick Sort.

Which sorting algorithm is used in Java’s Arrays.sort() for objects?

TimSort.