DS - Sorting Techniques

Merge Sort in Data Structures

Merge Sort is a popular Divide and Conquer algorithm used to sort arrays or lists efficiently. It works by recursively dividing the array into smaller halves, sorting them, and then merging the sorted halves back together.

⚙️ How Merge Sort Works
Divide: Split the array into two halves until each sub-array has only one element.
Conquer: Recursively sort each half.
Merge: Combine the sorted halves into a single sorted array.

🏷️ Time and Space Complexity

n = number of elements in the array
Merge Sort is stable, meaning it maintains the relative order of equal elements.

Program:

 1#include <stdio.h>
 2#define max 8
 3int arr[max]; // we have defined array globally.
 4void mergesort(int low, int high);
 5void merge(int low, int mid, int high);
 6void main()
 7{
 8    int i, j;
 9    printf("enter the elements\n");
10    for (i = 0; i < 8; i++)
11    {
12        scanf("%d", &arr[i]);
13    }
14    mergesort(0, 7);
15    printf("Sorted list is as follows:\n");
16    for (i = 0; i <= 7; i++)
17        printf("%d\n", arr[i]);
18}
19
20void mergesort(int low, int high)
21{
22    if (low != high)
23    {
24        int mid;
25        mid = (low + high) / 2;
26        mergesort(low, mid);
27        mergesort(mid + 1, high);
28        merge(low, mid, high);
29    }
30}
31
32void merge(int low, int mid, int high)
33{
34    int temp[max];
35    int i = low;
36    int k = low;
37    int j = mid + 1;
38    while ((i <= mid) && (j <= high))
39    {
40        if (arr[i] <= arr[j])
41            temp[k++] = arr[i++];
42        else
43            temp[k++] = arr[j++];
44    }
45    while (i <= mid)
46        temp[k++] = arr[i++];
47    while (j <= high)
48        temp[k++] = arr[j++];
49    for (i = low; i <= high; i++)
50    {
51        arr[i] = temp[i];
52    }
53}

✅ Why Use Merge Sort?

1. Efficient for large datasets.
   
2. Stable sorting (preserves equal elements' order).
   
3. Preferred for sorting linked lists because it doesn’t require random access.
   
   

Heap Sort in Data Structures

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap from the input data and then repeatedly removing the largest element from the heap and placing it at the end of the array.

🔍 Key Concepts
Binary Heap: A complete binary tree where each parent node is greater than or equal to its child nodes (in the case of a max heap).
Max Heap: The largest element is always at the root.
Min Heap: The smallest element is always at the root (used for finding the minimum, but not typically used in heap sort).

⚙️ How Heap Sort Works

1. Build a Max Heap from the unsorted array.
2. Swap the root (maximum value) with the last element.
3. Heapify the root of the reduced heap to maintain the max heap property.
4. Repeat steps 2–3 until the array is sorted.

🏷️ Time and Space Complexity

Program:

 1#include <stdio.h>
 2void maxheapify(int a[], int, int);
 3void maxheap(int a[], int beg, int end)
 4{
 5    int i;
 6    for (i = end / 2; i >= beg; i--)
 7    {
 8        maxheapify(a, i, end);
 9    }
10}
11
12void maxheapify(int a[], int f, int size)
13{
14    int max = f;
15    int l = f * 2, r = f * 2 + 1, t;
16
17    if (l <= size && a[l] > a[max])
18        max = l;
19    if (r <= size && a[r] > a[max])
20        max = r;
21    if (f != max)
22    {
23        t = a[f];
24        a[f] = a[max];
25        a[max] = t;
26        maxheapify(a, max, size);
27    }
28}
29
30void heapsort(int a[], int size)
31{
32    int i, t;
33    for (i = size; i >= 2; i--)
34    {
35        t = a[1];
36        a[1] = a[i];
37        a[i] = t;
38        maxheapify(a, 1, i - 1);
39    }
40}
41
42int main()
43{
44    int a[10], i;
45    printf("Enter array elements:\n");
46    for (i = 1; i < 10; i++)
47    {
48        scanf("%d", &a[i]);
49    }
50
51    maxheap(a, 1, 9);
52    heapsort(a, 9);
53    printf("Sorted array:\n");
54    for (i = 1; i < 10; i++)
55    {
56        printf("%d", a[i]);
57        printf("\n");
58    }
59}

✅ Advantages of Heap Sort

• Time-efficient: Always runs in O(n log n) time.
  
• In-place: Requires only a constant amount O(1) of additional memory.
  
• No recursion: Unlike merge sort, it doesn't use additional stacks for recursion.
  

❌ Disadvantages

• Not stable: Equal elements might not maintain their original order.
  
• Cache performance: Poorer than other algorithms like quicksort due to non-sequential memory access.
  

Quick Sort in Data Structures

Quick Sort is a highly efficient Divide and Conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays:

• Elements less than the pivot
• Elements greater than the pivot The process is recursively applied to the sub-arrays until the entire array is sorted.

🔍 Key Concepts
Pivot Selection: You can choose the first element, last element, middle element, or even a random element as the pivot.
Partitioning: Rearranges the elements so that elements smaller than the pivot are on the left and greater ones are on the right.
Recursion: The same process is applied recursively to the left and right sub-arrays.

⚙️ How Quick Sort Works

1. Choose a pivot element.
2. Rearrange the elements so that all elements less than the pivot are on the left, and those greater are on the right.
3. Recursively apply the same logic to the left and right sub-arrays.

🏷️ Time and Space Complexity

n = number of elements in the array
Not stable (equal elements may not maintain their original order)

Program:

 1#include <stdio.h>
 2#define max 8
 3int arr[max];
 4void quicksort(int low, int high);
 5int partition(int low, int high);
 6int main()
 7{
 8    int i;
 9    printf("Enter the elements:\n");
10    for (i = 1; i <= max; i++)
11        scanf("%d", &arr[i]);
12    quicksort(1, 8);
13    printf("Sorted list is as follows:\n");
14    for (i = 1; i <= max; i++)
15        printf("%d\n", arr[i]);
16}
17
18void quicksort(int low, int high)
19{
20    if (low < high)
21    {
22        int pi = partition(low, high);
23        quicksort(low, pi - 1);
24        quicksort(pi + 1, high);
25    }
26}
27
28int partition(int low, int high)
29{
30    int pivot = arr[high];
31    int i = low - 1, j, temp;
32    for (j = low; j <= high - 1; j++)
33    {
34        if (arr[j] < pivot)
35        {
36            i++;
37            temp = arr[i];
38            arr[i] = arr[j];
39            arr[j] = temp;
40        }
41    }
42    temp = arr[i + 1];
43    arr[i + 1] = arr[high];
44    arr[high] = temp;
45    return (i + 1);
46}

✅ Advantages of Quick Sort

• Efficient for large datasets.
• Requires less memory than merge sort (in-place sorting).
• Generally faster than other O(n log n) algorithms in practice.
  

❌ Disadvantages

• Not stable (equal elements may lose their relative order).
• Worst-case time complexity is O(n²) (rare but possible if the pivot is poorly chosen, like already sorted arrays).