Merge Sort

Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted) Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list. In the case of linked lists, the case is different mainly due to the difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike an array, in the linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore, the merge operation of merge sort can be implemented without extra space for linked lists.

Time Complexity : O(nlog(n))
- Average : Θ(nlog(n)), where n is size of array.
- Best : Ώ(nlog(n)), where n is size of array.
Space Complexity : O(n), where n is size of array.

Quick Sort

Quicksort is an algorithm used to quickly sort items within an array no matter how big the array is. It is quite scalable and works relatively well for small and large data sets, and is easy to implement with little time complexity. It does this through a divide-and-conquer method that divides a single large array into two smaller ones and then repeats this process for all created arrays until the sort is complete.

Time Complexity : O(n² )
- Average : Θ(nlog(n)), where n is size of array.
- Best : Ώ(nlog(n)), where n is size of array.
Space Complexity : O(log(n)), where n is size of array.

Insertion Sort

In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array. In an insertion sort, each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array and inserts it there. The iteration continues until the whole list is sorted.

Time Complexity : O(n² )
- Average : Θ(n²), where n is size of array.
- Best : Ώ(n), where n is size of array.
Space Complexity : O(1).

Heap Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

Time Complexity : O(nlog(n))
- Average : Θ(nlog(n)), where n is size of array.
- Best : Ώ(nlog(n)), where n is size of array.
Space Complexity : O(1).

Selection Sort

The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Time Complexity : O(n² )
- Average : Θ(n²), where n is size of array.
- Best : Ώ(n² ), where n is size of array.
Space Complexity : O(1).

Bubble Sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list. This simple algorithm performs poorly in real world use and is used primarily as an educational tool. More efficient algorithms such as quicksort, timsort, or merge sort are used by the sorting libraries built into popular programming languages such as Python and Java.

Time Complexity : O(n² )
- Average : Θ(n²), where n is size of array.
- Best : Ώ(n), where n is size of array.
Space Complexity : O(1).

        
          void merge(int *Arr, int start, int mid, int end) {
              int temp[end - start + 1];
              int i = start, j = mid+1, k = 0;
              while(i <= mid && j <= end) {
                    if(Arr[i] <= Arr[j]) {
                        temp[k++] = Arr[i++];
                    }
                    else {
                        temp[k++] = Arr[j++];
                    }
              }
              while(i <= mid) {
                  temp[k++] = Arr[i++];
              }
              while(j <= end) {
                  temp[k++] = Arr[j++];
              }
              for(i = start; i <= end; i += 1) {
                  Arr[i] = temp[i - start]
              }
          }
          
          void mergeSort(int *Arr, int start, int end) {
              if(start < end) {
                  int mid = (start + end) / 2;
                  mergeSort(Arr, start, mid);
                  mergeSort(Arr, mid+1, end);
                  merge(Arr, start, mid, end);
              }
          }


          int partition (int arr[], int low, int high){
              int pivot = arr[high];
              int i = (low - 1); 
              for (int j = low; j <= high- 1; j++){
                  if (arr[j] <= pivot){
                      i++;   
                      swap(arr[i], arr[j]);
                  }
              }
              swap(arr[i + 1], arr[high]);
              return (i + 1);
          }
          void quicksort(int a[], int p, int r)    {
              if(p < r){
                  int q;
                  q = partition(a, p, r);
                  quicksort(a, p, q-1);
                  quicksort(a, q+1, r);
              }
          }


        void insertionSort(int arr[], int n){
            int i, key, j;
            for (i = 1; i < n; i++){
                key = arr[i];
                j = i - 1;
                while (j >= 0 && arr[j] > key){
                    arr[j + 1] = arr[j];
                    j = j - 1;
                }
                arr[j + 1] = key;
            }
      }


        void heapify(int arr[], int n, int i){
            int largest = i;
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            if (l < n && arr[l] > arr[largest])
                largest = l;
        
            if (r < n && arr[r] > arr[largest])
                largest = r;
        
            if (largest != i) {
                swap(arr[i], arr[largest]);
                heapify(arr, n, largest);
            }
        }
        void heapSort(int arr[], int n){
            for (int i = n / 2 - 1; i >= 0; i--)
                heapify(arr, n, i);
        
            for (int i = n - 1; i > 0; i--) {
                swap(arr[0], arr[i]);
                heapify(arr, i, 0);
            }
        }


        void selectionSort(int arr[], int n){
            int i, j, min_idx;
            for (i = 0; i < n-1; i++){
                min_idx = i;
                for (j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
        
                swap(arr[min_idx], arr[i]);
            }
        }


        void bubbleSort(int arr[], int n){
            int i, j;
            for (i = 0; i < n-1; i++)    
            for (j = 0; j < n-i-1; j++)
                if (arr[j] > arr[j+1])
                    swap(arr[j], arr[j+1]);
        }