Sorting #

Comparison-based sorting
Stable sorting
In-place sorting

What is a stable sorting algorithm? #

Sorting algorithms that maintain the relative order of records with equal keys are called stable.

Ref: Baeldung

Comparison Table #

Cyclic Sort #

Cyclic sort is not stable.

Why is it called cyclic? Because this sorting technique can only be applied on cycles within an array or list. Cycles are nothing but subsequences of unsorted elements. A cycle occurs when there is an element in the array/list out-of-place, and moving the element to its correct position in the array/list moves another element to the former element’s place, forming a cycle.

Where should we use cyclic sort?

Can we use cyclic sort where the elements are not consecutive numbers (e.g., 1-n)? Can we use if the elements are not in a subsequence? Cyclic sort can be used to sort elements in a subsequence. In case of integer arrays, it is not encessary that the elements in a subsequence are consecutive integers (e.g., 1,2,3,4). As long as the integers in a subsequence form a series it can sorted using cyclic sort (e.g., 2, 4, 6)

What is a subsequence? Is it different from a cycle?

Problems #

How to make a non-stable sort into a stable sort? #

How to make an in-place sort into an in-place sort? #

How does each of the above sorting algorithm behave with duplicate elements? #

Implement a non-comparison sorting algorithm #

Merge k-sorted arrays #

(a) Out-of-place (i.e., when new memory allocations are allowed)

(b) In-place (i.e., when one array is large enough to hold all arrays and has empty slots)

(c) Compute intersection of k-sorted arrays

Can we use the same solutions for the above problems if the data structure is list, instead of array?

Sorting lists #

(a) Implement a fast sorting algorithm for lists

Sorting with duplicates #

(a) Sort array with duplicate values

(b) Remove first-name duplicates

(c) Partitioning and sorting an array with repeated entries