Sorting is the process of arranging data in a specific order - typically in ascending or descending sequence - based on one or more keys or criteria.

Sorting is a fundamental operation in computer science used to organise, search, analyze, and optimize data processing.

Common Ordering Criteria

1. Numerical Sorting: Sorting based on numeric values, either ascending (low to high) or descending (high to low).

 Input: [1, 3, 2, 10, 5]
 Output (Ascending): [1, 2, 3, 5, 10]
 Output (Descending): [10, 5, 3, 2, 1]
 

2. Lexicographic (Alphabetical) Sorting: Sorting strings based on the dictionary order, comparing characters from left to right using Unicode or ASCII values.

 Input: ["banana", "apple", "zebra", "grape"]
 Output: ["apple", "banana", "grape", "zebra"]
 

3. Custom Key Sorting: Sorting using a custom property or attribute of an object or record, not the entire object itself.

 students = [
  {"name": "Alice", "age": 25},
  {"name": "Bob", "age": 20},
  {"name": "Charlie", "age": 22}
 ]
 

 [
  {"name": "Bob", "age": 20},
  {"name": "Charlie", "age": 22},
  {"name": "Alice", "age": 25}
 ]
 

4. Multi-Key Sorting (Compound Sort): Sort by multiple keys, in a specified order. If the first keys are equal, the second (or third…) keys determine the order.

 people = [
  {"first": "John", "last": "Smith"},
  {"first": "Alice", "last": "Smith"},
  {"first": "Bob", "last": "Anderson"}
 ]
 

 [
  {"first": "Bob", "last": "Anderson"},
  {"first": "Alice", "last": "Smith"},
  {"first": "John", "last": "Smith"}
 ]
 

Stable Sorting

A stable sorting algorithm preserves the relative order of records that have equal keys (or values).

 Input:
 [
  {name: "Alice", age: 25},
  {name: "Bob", age: 25},
  {name: "Charlie", age: 20}
 ]
 

 [
  {name: "Charlie", age: 20},
  {name: "Alice", age: 25},
  {name: "Bob", age: 25}
 ]
 

Unstable Sorting

An unstable sorting algorithm may change the relative order of records with equal keys.

An unstable sort may return:

 [
  {name: "Charlie", age: 20},
  {name: "Alice", age: 25},
  {name: "Bob", age: 25}
 ]
 

Bubble vs Selection vs Insertion

1. Given an array of integers. Design the following sorting algorithms:

1. Bubble Sort
2. Selection Sort
3. Insertion Sort

Each algorithms should sort the input array in:

• Ascending order
• Descending order

Each algorithms should return both sorted arrays.

0s 1s 2s in Order

2. Given an array consisting only of integers 0, 1, and 2. Design an algorithm that sort the array in-place.

Sort K-Sorted Array

3. Given an array of n integers, where each element is at most k positions away from its correct position in the fully sorted array.

Design an algorithm to sort the array.

An array is said to be k-sorted (or nearly sorted) if the element that should be at index i in the sorted array is located somewhere in the range [i - k, i + k] in the unsorted array.

Kth Smallest or Largest Element

4. Given an unsorted array of n integers and an integer k. Design an algorithm to find and return:

• The kth smallest element
• The kth largest element

kth smallest = the value that would be at index k-1 if the array were sorted in ascending order.

kth largest = the value that would be at index n-k if the array were sorted in ascending order.

Merge Sort vs Quick Sort

1. Given an array of integers. Design the following sorting algorithms:

1. Merge Sort
2. Quick Sort

Each algorithm should sort the array in ascending order and return the sorted array.

Merge Sorted Arrays

2. Given multiple sorted arrays in ascending order.

Design an algorithm that merges all the arrays into a single sorted array.

Linked List Sort

3. Given a head of a singly linked list containing integers.

Design an algorithm that sort the linked list in ascending order and returns the head of the sorted list.

Linked List Node structure -

    class ListNode {
        constructor(value = 0, next = null) {
            this.value = value;
            this.next = next;
        }
    }
 

Stable Sort with Duplicates

4. Given an array of integers that may contain duplicate values. Design an algorithm that stable sorts the array in ascending order.

Inversion Count in Array

5. Given an array of integers. Desing an algorithm that count the total number of inversions in the array.

An inversion is a measure of how far a list is from being sorted. If nums[i] > nums[j] and i < j, that is an inversion.

Sort Characters by Frequency

6. Given a string s consisting of ASCII characters (letters, digits, symbols). Design an algorithm that rearranges the characters of s so that they appearin descending order of frequency.

If multiple characters have the same frequency, they can appear in any order relative to each other.

The output string must include all characters the number of times they appear in the original string.