Radix Sort

Radix sort is a non-comparative sorting algorithm that works on integers by grouping numbers by their individual digits or by their position in the number. It's based on the principle of sorting numbers by their individual digits from the least significant digit (rightmost) to the most significant digit (leftmost).

Working of Radix sort Algorithm:

Determine the Maximum Number of Digits: Find the maximum number of digits among all the numbers in the input array. This will help determine the number of passes needed for the sorting process.

Initialize Buckets: Create 10 buckets, each representing a digit (0-9).

Iterate Through Each Digit Position: Starting from the least significant digit (rightmost), perform the following steps for each digit position:

• Place Numbers in Buckets: Iterate through the input array and place each number into the appropriate bucket based on the value of the current digit.
• Combine Buckets: After placing all numbers into buckets, combine the buckets back into the original array order.

Repeat for Each Digit Position: Repeat step 3 for each subsequent digit position, moving from right to left (least significant digit to most significant digit).

Return Sorted Array: After sorting based on all digits, the array will be sorted in non-decreasing order.

Algorithm to implement Radix sort

ALGORITHM RadixSort(A[0..n − 1])
// Sorts a given array by radix sort
// Input: An array A[0..n − 1] of integers
// Output: Array A[0..n − 1] sorted in non-decreasing order

// Find the maximum number of digits in the array
maxDigits ← getMaxDigits(A)

// Iterate through each digit position, starting from the least significant digit
for d ← 0 to maxDigits - 1 do
    // Initialize buckets
    buckets[10][]

    // Place numbers in buckets based on the value of the current digit
    for i ← 0 to n - 1 do
        digit ← getDigit(A[i], d)
        buckets[digit].append(A[i])

    // Combine buckets back into the original array order
    index ← 0
    for i ← 0 to 9 do
        for each number in buckets[i] do
            A[index] ← number
            index ← index + 1

Sort the given list of numbers using Radix sort: 

Initial List: 12, 23, 55, 77, 82, 100, 150, 901

Sort the given list of numbers using Radix sort: 92,501,200,15,150,88,44,23

Mergesort

Mergesort is a perfect example of a successful application of the divide-and- conquer technique. It sorts a given array A[0..n − 1] by dividing it into two halves A[0..⌊n/2⌋ − 1] and A[⌊n/2⌋..n − 1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

Algorithm for Merge sort

ALGORITHM MergeSort(A[0..n - 1])
// Sorts array A[0..n - 1] using recursive merge sort
// Input: An array A[0..n - 1] of orderable elements
// Output: Array A[0..n - 1] sorted in nondecreasing order

if n > 1 then
    // Divide the array into two subarrays
    copy A[0..⌊n/2⌋ - 1] to B[0..⌊n/2⌋ - 1]
    copy A[⌊n/2⌋..n - 1] to C[0..⌈n/2⌉ - 1]
    
    // Recursively sort the subarrays
    MergeSort(B[0..⌊n/2⌋ - 1])
    MergeSort(C[0..⌈n/2⌉ - 1])
    
    // Merge the sorted subarrays
    Merge(B[0..⌊n/2⌋ - 1], C[0..⌈n/2⌉ - 1], A[0..n - 1])

Algorithm to merge the list

ALGORITHM Merge(B[0..p - 1], C[0..q - 1], A[0..p + q - 1])
// Merges two sorted arrays into one sorted array
// Input: Arrays B[0..p - 1] and C[0..q - 1] both sorted
// Output: Sorted array A[0..p + q - 1] containing elements of B and C

i ← 0; j ← 0; k ← 0
while i < p and j < q do
    if B[i] ≤ C[j] then
        A[k] ← B[i]
        i ← i + 1
    else
        A[k] ← C[j]
        j ← j + 1
    k ← k + 1
    
if i = p then
    // Copy remaining elements of C to A
    copy C[j..q - 1] to A[k..p + q - 1]
else
    // Copy remaining elements of B to A
    copy B[i..p - 1] to A[k..p + q - 1]

Sort the given list of numbers using merge sort: 8, 3, 2, 9, 7, 1, 5, 4​​​​​​​