Sorting

Sorting refers to the process of arranging data in a particular order, typically ascending or descending. Efficient sorting is crucial for optimizing the performance of other algorithms (such as search and merge operations) and for presenting data in a human-readable format.

Types of Sorting Algorithms

Sorting algorithms can be broadly classified based on their approach, stability, and time complexity. Here are some of the most common types:

1. Bubble Sort

A simple comparison-based algorithm that repeatedly steps through the list compares adjacent elements and swaps them if they are in the wrong order. It is easy to implement but inefficient for large datasets.

Time Complexity: O(n²)
Space Complexity: O(1)
Stable: Yes

fun bubbleSort(arr: MutableList<Int>) {
    var swap = false
    for(i in 0 until arr.size) {
        swap = false
        for (j in 1 until arr.size - i) {
            if (arr[j - 1] > arr[j])
                arr[j - 1] = arr[j].also { arr[j] = arr[j - 1]; swap = true }
        }
        if(!swap) return
    }
}

2. Selection Sort

This algorithm divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly selects the smallest (or largest) element from the unsorted sublist and moves it to the end of the sorted sublist.

Time Complexity: O(n²)
Space Complexity: O(1)
Stable: No

fun selectionSort(arr: MutableList<Int>) {
    for(i in 0 until arr.size) {
        var smallest = i
        for(j in i + 1 until arr.size) {
            if(arr[j] < arr[smallest]) {
                smallest = j
            }
        }
        arr[i] = arr[smallest].also { arr[smallest] = arr[i] }
    }
}

3. Insertion Sort

Builds the final sorted array one item at a time. It is efficient for small datasets and mostly sorted arrays.

Time Complexity: O(n²)
Space Complexity: O(1)
Stable: Yes

fun insertionSort(arr: MutableList<Int>) {
    for(i in 1 until arr.size) {
        for(j in i downTo 0) {
            if(arr[j] < arr[j - 1]) {
                arr[j] = arr[j-1].also{arr[j - 1] == arr[j] }
            } else break
        }
    }
}

4. Shell Sort

An optimization over insertion sort that allows the exchange of far-apart elements. It uses a gap sequence to compare and sort elements.

Time Complexity: Depends on gap sequence (best: O(n log n), worst: O(n²))
Space Complexity: O(1)
Stable: No

fun shellSort(arr: MutableList<Int>) {
    var gap = arr.size / 2
    while (gap > 0) {
        for (i in gap until arr.size) {
            val temp = arr[i]
            var j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap /= 2
    }
}

5. Merge Sort

A divide-and-conquer algorithm that divides the array into halves, sorts them, and then merges the sorted halves. It is efficient and stable.

Time Complexity: O(n log n)
Space Complexity: O(n)
Stable: Yes

fun mergeSort(arr: MutableList<Int>, l: Int, r: Int) {
    if (r - l <= 1) return
    val mid = (r + l) / 2
    mergeSort(arr, 0, mid)
    mergeSort(arr, mid, r)
    merge(arr, l, mid, r)
}

fun merge(arr: MutableList<Int>, l: Int, m: Int, r: Int) {
    val n1 = m - l + 1
    val n2 = r - m
    val left = MutableList(n1) { arr[l + it] }
    val right = MutableList(n2) { arr[m + 1 + it] }
    var i = 0
    var j = 0
    var k = l
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++]
        } else {
            arr[k++] = right[j++]
        }
    }
    while (i < n1) {
        arr[k++] = left[i++]
    }
    while (j < n2) {
        arr[k++] = right[j++]
    }
}

6. Quick Sort

Another divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot. It is very efficient for large datasets.

Time Complexity: O(n log n) average, O(n²) worst
Space Complexity: O(log n)
Stable: No

fun quickSort(arr: MutableList<Int>, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

fun partition(arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[high]
    var i = low - 1
    for (j in low until high) {
        if (arr[j] <= pivot) {
            i++
            arr[i] = arr[j].also { arr[j] = arr[i] }
        }
    }
    arr[i + 1] = arr[high].also { arr[high] = arr[i + 1] }
    return i + 1
}

Randomized Quick Sort

A variation where the pivot is chosen randomly to avoid worst-case scenarios.

7. Tree Sort

Use a binary search tree to insert all elements and then perform an in-order traversal to retrieve them in sorted order.

Time Complexity: O(n log n) average, O(n²) worst
Space Complexity: O(n)
Stable: Yes (if self-balancing tree is used)

8. Counting Sort

A non-comparison-based algorithm suitable for sorting integers within a specific range. It counts the occurrences of each value and calculates their positions.

Time Complexity: O(n + k) where k is the range of input
Space Complexity: O(k)
Stable: Yes

fun countingSort(arr: MutableList<Int>) {
    val min = arr.min()
    val k = arr.max() - min
    val c = IntArray(k) { 0 }
    arr.forEach { c[it - min] += 1 }
    var i = 0
    for(j in 0 until k) {
        while(c[j] > 0) {
            arr[i++] = j - min
            c[j]--
        }
    }
}

9. Bucket Sort

Divides the input into several buckets and sorts each bucket individually (often using another sorting algorithm). Suitable for uniformly distributed data.

Time Complexity: O(n + k)
Space Complexity: O(n + k)
Stable: Yes

fun bucketSort(arr: MutableList<Int>) {
    if (arr.isEmpty()) return
    val minValue = arr.minOrNull() ?: return
    val maxValue = arr.maxOrNull() ?: return
    val bucketCount = arr.size
    val buckets = Array<MutableList<Int>>(bucketCount) { mutableListOf() }
    val range = (maxValue - minValue + 1).toDouble() / bucketCount
    for (num in arr) {
        val idx = ((num - minValue) / range).toInt().coerceAtMost(bucketCount - 1)
        buckets[idx].add(num)
    }
    arr.clear()
    for (bucket in buckets) {
        bucket.sort() // Any sorting algorithm can be used
        arr.addAll(bucket)
    }
}

10. Radix Sort

Processes integer keys by individual digits, starting from the least significant digit to the most significant. It uses a stable sub-sorting algorithm (like counting sort) for each digit.

Time Complexity: O(nk) where k is the number of digits
Space Complexity: O(n + k)
Stable: Yes

11. External Sorting

Used for massive datasets that do not fit into memory. It divides data into manageable chunks, sorts them in memory, and then merges the sorted chunks.

Examples: Given 900 Mb data on disk, sort it using 100 Mb RAM.

Read 100 Mb of data, sort it and write it to disk.
Read the next 100 Mb data sort it and write to disk. Repeat for all chunks.
Read 10 Mb from each sorted chunk (9 chunks total) and the remaining 10 Mb for buffer.
Using merge logic from merge sort, write the merge results into buffer. When the output buffer is full, flush it to the disk. When any of 10Mb is used, load the next 10Mb from the chunks.

Stability in Sorting

A sorting algorithm is stable if it preserves the relative order of equal elements. Stability is important when sorting records with multiple fields.

Comparison of Sorting Algorithms

Algorithm	Time Complexity	Space Complexity	Stable
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	No
Insertion Sort	O(n²)	O(1)	Yes
Shell Sort	O(n log n)*	O(1)	No
Merge Sort	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)*	O(log n)	No
Tree Sort	O(n log n)*	O(n)	Yes
Counting Sort	O(n + k)	O(k)	Yes
Bucket Sort	O(n + k)	O(n + k)	Yes
Radix Sort	O(nk)	O(n + k)	Yes
External Sorting	O(n log n)	O(n)	Depends

*Depends on implementation and input data.

Choosing the Right Sorting Algorithm

For small or nearly sorted datasets: Insertion Sort
For large datasets in memory: Merge Sort or Quick Sort
For data with a small range of integer keys: Counting Sort, Radix Sort, or Bucket Sort
For massive datasets (external storage): External Sorting