This following article explains how to implement Heap Sort in C#.

**What is Heap Sort?**

In brief, Heap sort is a comparison-based sorting algorithm that sorts an array by using a binary heap data structure. Moreover, it’s an efficient and stable sorting algorithm. Evidently, it has a time complexity of O(n log n).

Actually, the algorithm works by dividing the input array into two parts: the sorted part and the unsorted part. Further, the sorted part is built up at the end of the array while the unsorted part is reduced towards the beginning of the array. Then, the algorithm repeatedly selects the maximum element from the unsorted part of the array. After that, it moves it to the end of the sorted part. Meanwhile, the process continues until the unsorted part is empty.

As a matter of fact, Heap sort is a useful sorting algorithm for sorting arrays of numbers or other comparable objects. However, it’s not as widely used as other sorting algorithms like quicksort or merge sort. Still it has its own advantages. To that end, it returns a guaranteed O(n log n) performance. Most important feature of Heap Sort is its ability to sort elements that are not in a contiguous memory block. The following code shows its implementation in C#.

**Implementation of Heap Sort in C#**

```
using System;
class HeapSort
{
public static void Sort(int[] arr)
{
int n = arr.Length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
Heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
static void Heapify(int[] arr, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
Heapify(arr, n, largest);
}
}
}
class Program
{
static void Main(string[] args)
{
int[] arr = {12, 11, 13, 5, 6, 7};
int n = arr.Length;
HeapSort.Sort(arr);
Console.WriteLine("Sorted array is:");
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
}
}
```

**Output**

**Further Reading**

Parameter and ParameterCollection in ADO.NET

Database Manipulation Using DataGrid

- Angular
- ASP.NET
- C
- C#
- C++
- CSS
- Dot Net Framework
- HTML
- IoT
- Java
- JavaScript
- Kotlin
- PHP
- Power Bi
- Python
- Scratch 3.0
- TypeScript
- VB.NET

Princites