Unit 6: Efficient Sorting Algorithms & Analysis - Subjective Questions

sorting algorithms are algorithms whose running time grows proportionally to the product of the number of elements and . Merge sort, heap sort, and average-case quick sort are common examples.

Significance:

• Comparison-based sorting algorithms determine order by comparing pairs of elements.
• A comparison sort can be represented by a binary decision tree.
• Sorting distinct elements requires distinguishing among possible permutations.
• Therefore, the decision tree must have at least leaves and height at least .
• Since , every general comparison-based sorting algorithm requires at least comparisons in the worst case.

Thus, algorithms with worst-case complexity are asymptotically optimal among comparison-based sorting algorithms.

Merge sort divides an array of size into two halves, recursively sorts both halves, and merges the sorted halves.

Its recurrence is:

Here:

• represents sorting two sub-arrays of size .
• represents the time required to merge them.

Using the Master Theorem, , , and . Since:

and have the same order. Therefore:

There are levels in the recursion tree, and each level performs merging work. Hence, merge sort takes time in the best, average, and worst cases.

Recursive merge sort repeatedly divides the array until every sub-array contains at most one element. It then merges adjacent sub-arrays in sorted order.

Algorithm:

• Find the middle index.
• Recursively sort the left half.
• Recursively sort the right half.
• Merge the two sorted halves.

Illustration:

• Divide into and .
• Sort the left half: .
• Sort the right half: .
• Merge and .
• The final sorted array is .

The algorithm requires time and auxiliary space. It is stable because equal elements can retain their original relative order during merging.

Iterative merge sort, also called bottom-up merge sort, starts with sub-arrays of size one and repeatedly merges adjacent sorted blocks.

Procedure:

• Treat every element as a sorted block of size .
• Merge adjacent blocks to create blocks of size .
• Merge blocks of size to create blocks of size .
• Continue with sizes until the block size is at least .

Differences from recursive merge sort:

• Iterative merge sort uses loops; recursive merge sort uses recursive calls.
• Iterative merge sort does not require a recursion stack.
• Recursive merge sort divides top-down, whereas iterative merge sort combines bottom-up.
• Both require time and typically auxiliary space.
• Both can be stable when equal elements are selected from the left block first.

The iterative form can avoid function-call overhead and recursion-depth concerns.

The merge operation combines two sorted sub-arrays into one sorted sequence.

Steps:

• Maintain one pointer at the beginning of each sorted sub-array.
• Compare the elements referenced by the two pointers.
• Copy the smaller element into a temporary array and advance its pointer.
• Repeat until one sub-array is exhausted.
• Copy all remaining elements from the other sub-array.
• Copy the merged result back to the original array if required.

If the two sub-arrays contain and elements, each element is examined and copied a constant number of times. Therefore, the running time is:

For a merge involving a total of elements, this becomes . Choosing the left element when values are equal preserves stability.

Quick sort selects a pivot, partitions the array around the pivot, and recursively sorts the two resulting partitions.

Using as the pivot for :

• Elements smaller than or equal to are moved to the left.
• Elements greater than are moved to the right.
• After partitioning, one valid arrangement is .
• The pivot is now in its final sorted position.
• Quick sort is then applied to and .
• The final sorted array is .

Complexities:

• Best and average cases: .
• Worst case: .
• Average recursion space: .

Standard in-place quick sort is generally not stable.

Lomuto partition:

• Commonly chooses the last element as the pivot.
• Maintains an index separating elements smaller than or equal to the pivot from larger elements.
• Makes one forward scan through the partition.
• Is simple to understand and implement.
• Usually performs more swaps, especially when duplicate values are present.
• Returns the pivot's final position.

Hoare partition:

• Commonly chooses the first or middle element as the pivot.
• Uses two indices that move inward from opposite ends.
• Swaps elements found on the wrong sides of the pivot.
• Usually performs fewer swaps than Lomuto partition.
• Returns a partition boundary; the returned index is not necessarily the pivot's final position.

Both schemes partition in time, but their recursion boundaries differ. Mixing one scheme's partition function with the other scheme's recursive ranges can cause incorrect results or infinite recursion.

In the best case, each pivot divides the array into two nearly equal partitions:

There are levels, and each level performs partitioning work. Thus:

In the worst case, the pivot repeatedly produces partitions of sizes and :

Expanding the recurrence gives:

Ways to reduce the chance of the worst case:

• Select a random pivot.
• Use median-of-three pivot selection.
• Use three-way partitioning when many duplicate values exist.
• Recurse on the smaller partition first and process the larger one iteratively to limit stack depth.
• Switch to insertion sort for very small partitions.

Randomized pivot selection gives expected time for arbitrary input order.

Merge sort:

• Has time in the best, average, and worst cases.
• Typically requires auxiliary memory for arrays.
• Is stable when implemented correctly.
• Performs well on linked lists and external data.
• Has predictable performance.

Quick sort:

• Has average-case time and worst-case time .
• Can sort arrays in place, with average recursion space .
• Is generally not stable.
• Often performs well for in-memory arrays because of cache locality and low constant factors.
• Its performance depends on pivot selection and partition balance.

Merge sort is preferred when stability or guaranteed worst-case performance is important. Quick sort is often preferred for internal array sorting when memory usage and practical speed are priorities.

To sort elements by frequency, first count how many times each distinct value occurs and then arrange values according to those counts.

Efficient approach:

• Traverse the array and store each value's frequency in a hash map.
• If ties must preserve first appearance, also store the first index of each value.
• Sort the distinct values using a comparator that orders:
  • Higher frequency before lower frequency.
  • For equal frequencies, smaller value or earlier first occurrence, depending on the requirement.
• Append each distinct value to the result as many times as its frequency.

If there are elements and distinct values:

• Frequency counting takes expected time.
• Sorting the distinct values takes time.
• Constructing the result takes time.

The total expected time is , which is at most .

First compute the frequencies:

• occurs times.
• occurs times.
• occurs times.
• occurs time.

The frequencies are all different, so the tie-breaking rule is not needed in this example.

Ordering the values by decreasing frequency gives:

Repeating each value according to its frequency produces:

A hash map can count frequencies in expected time. Sorting the distinct values takes time, and building the output takes time.

An efficient solution uses two boundary scans followed by minimum and maximum checks.

Procedure:

• Scan from left to right to find the first index such that .
• If no such index exists, the array is already sorted.
• Scan from right to left to find the first index such that .
• Find the minimum and maximum elements in .
• Move left while earlier elements are greater than the sub-array minimum.
• Move right while later elements are smaller than the sub-array maximum.

The final interval is the minimum sub-array that must be sorted. Its length is:

The method takes time and additional space.

Scan from the left:

• , but .
• Therefore, the initial left boundary is index using zero-based indexing.

Scan from the right:

• , , and , but .
• Therefore, the initial right boundary is index .

The candidate sub-array is .

• Its minimum is .
• Its maximum is .
• Elements before the boundary, , are not greater than .
• Elements after the boundary, , are not smaller than .

Thus, sorting indices through is sufficient. The minimum sub-array is , its sorted form is , and its length is .

Important special cases include:

• Already sorted array: No inversion exists, so no sub-array needs sorting. The required length may be reported as .
• Reverse-sorted array: The entire array usually needs to be sorted.
• Duplicate values: Boundaries must use strict comparisons carefully so equal adjacent values are handled correctly.
• Single-element array: It is already sorted, so the required length is .
• Disorder near an endpoint: The required interval may begin at index or end at index .
• Hidden boundary expansion: The first and last inversions are only initial boundaries. The minimum or maximum inside that interval may require extending it outward.

For example, in , the first inversion starts near , but the minimum value forces the left boundary to move before .

Lexicographic sorting arranges strings by comparing their characters from left to right, similar to dictionary order.

Comparison process:

• Compare the first characters of both strings.
• If they differ, their character ordering determines the result.
• If they are equal, continue to the next characters.
• Stop at the first unequal pair.
• If all compared characters match and one string ends, the shorter string comes first.

For example:

• apple comes before banana because a comes before b.
• car comes before card because car is a prefix of card.
• In a case-sensitive character encoding, uppercase and lowercase letters may have different ordering.

Sorting strings with a comparison sort generally requires string comparisons. If each comparison examines up to characters, the worst-case time can be expressed as .

Strings can be sorted using several criteria depending on the problem statement:

• Lexicographic order: Compare characters from left to right.
• Reverse lexicographic order: Apply lexicographic comparison in descending order.
• Length: Place shorter or longer strings first.
• Case-insensitive order: Compare normalized forms such as lowercase versions.
• Frequency: Sort strings according to how often they occur.
• Character count: Sort by the number of vowels, digits, or another selected character class.
• Numeric value: For strings representing numbers, compare numerical values rather than character order.
• Custom priority: Rank particular prefixes, suffixes, or categories first.

A comparator must define a consistent ordering. When primary keys are equal, a secondary key such as the original string or input position should be used to obtain deterministic output.

In case-specific sorting, characters are sorted while respecting a rule related to uppercase and lowercase letters. One common requirement is to preserve the case pattern at each position.

Approach:

• Extract all lowercase characters into one list.
• Extract all uppercase characters into another list.
• Sort both lists independently.
• Traverse the original string.
• At an originally lowercase position, place the next sorted lowercase character.
• At an originally uppercase position, place the next sorted uppercase character.

For example, consider gEeksF:

• Lowercase characters are g, e, k, s, which sort to e, g, k, s.
• Uppercase characters are E, F, which are already sorted.
• The original case pattern is lowercase, uppercase, lowercase, lowercase, lowercase, uppercase.
• Reconstructing with that pattern gives eEgksF.

The sorting step takes time, while extraction and reconstruction take time.

A case-insensitive comparator first compares normalized versions of the strings, usually by converting both to lowercase or using a language-provided case-folding operation.

Comparator logic:

• Compute normalized forms of both strings.
• Compare the normalized forms lexicographically.
• If they differ, return that comparison result.
• If they are equal, compare the original strings as a secondary key, or preserve input order using a stable sort.

For example, for Apple, apple, and APPLE, all normalized keys may be apple. A secondary rule is needed to define their final order.

Important considerations:

• A stable sort preserves the input order of equal normalized keys.
• Character case conversion may depend on locale.
• Unicode-aware case folding is more reliable than simple ASCII conversion for international text.
• Precomputing normalized keys avoids repeatedly converting strings during comparisons.

With comparison sorting, the typical complexity is for strings of maximum relevant length .

The task is to count distinct value pairs satisfying:

For , an efficient hash-set method is:

• Insert every array value into a set to remove duplicates.
• For every distinct value , check whether exists in the set.
• If it exists, count the pair once.

This avoids counting both and .

For , a pair exists only when the same value occurs at least twice. A frequency map is therefore required, and each value with frequency at least contributes one distinct pair.

Complexity:

• Expected time: with hashing.
• Additional space: .

Alternatively, sort the array and use two pointers in time, taking care to skip duplicates.

The distinct values are:

For each value , check whether exists:

• For , exists: .
• For , exists: .
• For , exists: .
• For , does not exist.
• For , exists: .
• Larger values do not produce additional pairs.

Therefore, the number of distinct pairs is:

The repeated occurrence of does not create another distinct pair because pairs are distinguished by their values rather than by their array indices. Using a set automatically removes such duplicate contributions.