In this article, we will discuss the grail sort. Grail sort is a sorting algorithm that was introduced by Vladimir Yaroslavskiy. It is an efficient sorting algorithm for large data sets that have a lot of duplicate values. The name “grail” refers to the fact that the algorithm is based on the idea of finding a “holy grail” of sorting algorithms that is both fast and capable of handling large amounts of duplicates.
Example:
Input: [7, 7, 4, 1, 5, 3, 2]
Output: [1, 2, 3, 4, 5, 7, 7]
Approach: To solve the problem follow the below steps:
- Divide the input array into blocks of size sqrt(n), where n is the length of the input array.
- Sort each block using a comparison-based sorting algorithm.
- Merge the sorted blocks into a single sorted array using an algorithm similar to merge sort.
- Repeat steps 2 and 3 until all blocks have been merged into a single sorted array.
Working of above approach:
- Divide the array into blocks of size 1:
- [7] [7] [4] [1] [5] [3] [2]
- Merge adjacent blocks:
- [7, 7] [1, 4] [3, 5] [2]
- Rotate the remaining blocks:
- [7, 7] [4, 1] [5, 3] [2]
- Merge adjacent blocks:
- [1, 4, 7, 7] [2, 3, 5]
- Divide the array into blocks of size 2:
- [1, 4] [7, 7] [2, 3] [5]
- Merge adjacent blocks:
- [1, 4, 7, 7] [2, 3, 5]
- Divide the array into blocks of size 4:
- [1, 4, 7, 7, 2, 3, 5]
- (8) Merge adjacent blocks:
- [1, 2, 3, 4, 5, 7, 7]
Below is the implementation for the above approach:
C++
// C++ implementation for the above approach.#include <algorithm>#include <cmath>#include <iostream>#include <limits>#include <vector>using namespace std;// grail sort for returning the sorted arrayvector<int> grailSort(vector<int> arr){ // Split the array into blocks of size sqrt(n) int blockSize = sqrt(arr.size()); int numBlocks = (arr.size() + blockSize - 1) / blockSize; vector<vector<int> > blocks(numBlocks); for (int i = 0; i < numBlocks; i++) { blocks[i].resize(blockSize); copy(arr.begin() + i * blockSize, arr.begin() + (i + 1) * blockSize, blocks[i].begin()); // copying values from array to blocks // Sort the blocks using insertion sort for (int j = 1; j < blockSize; j++) { int key = blocks[i][j]; int k = j - 1; while (k >= 0 && blocks[i][k] > key) { blocks[i][k + 1] = blocks[i][k]; k--; } blocks[i][k + 1] = key; } } // Merge the blocks using an algorithm // similar to merge sort and initialize // the pointers to the beginning of each block vector<int> pointers(numBlocks); vector<int> result; while (true) { // Find the minimum element among the // active blocks int minVal = numeric_limits<int>::max(); // minVal currently INT_MAX at start int minIdx = -1; for (int i = 0; i < numBlocks; i++) { if (pointers[i] < blocks[i].size() && blocks[i][pointers[i]] < minVal) { minVal = blocks[i][pointers[i]]; minIdx = i; } } // If all blocks are exhausted, we're done if (minIdx == -1) { break; } // Otherwise, add the minimum element // to the result and increment the // pointer for that block result.push_back(minVal); pointers[minIdx]++; } return result;}// Driver's codeint main(){ // Original Array vector<int> arr = { 7, 7, 4, 1, 5, 3, 2, 0 }; cout << "Input : "; for (auto x : arr) { cout << x << " "; } cout << endl; // Printing result vector<int> result = grailSort(arr); cout << "Output: "; for (auto x : result) { cout << x << " "; } cout << endl; return 0;}// Contributed by SR.Dhanush |
Java
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class GrailSort { // Grail sort for returning the sorted array public static List<Integer> grailSort(List<Integer> arr) { // Split the array into blocks of size sqrt(n) int blockSize = (int)Math.sqrt(arr.size()); // Determine the block size as // sqrt(n) int numBlocks = (arr.size() + blockSize - 1) / blockSize; // Calculate the number // of blocks needed List<List<Integer> > blocks = new ArrayList<>( numBlocks); // Create a list to hold the blocks for (int i = 0; i < numBlocks; i++) { blocks.add(new ArrayList<>(Collections.nCopies( blockSize, 0))); // Initialize each block with 0s Collections.copy( blocks.get(i), arr.subList(i * blockSize, Math.min((i + 1) * blockSize, arr.size()))); // Copy the elements // from the original // array to the // blocks // Sort the blocks using insertion sort for (int j = 1; j < blockSize; j++) { int key = blocks.get(i).get(j); int k = j - 1; while (k >= 0 && blocks.get(i).get(k) > key) { blocks.get(i).set(k + 1, blocks.get(i).get(k)); k--; } blocks.get(i).set(k + 1, key); } } // Merge the blocks using an algorithm // similar to merge sort and initialize // the pointers to the beginning of each block List<Integer> pointers = new ArrayList<>(Collections.nCopies( numBlocks, 0)); // Create a list to hold the pointers List<Integer> result = new ArrayList<>(); // Create a list to hold // the sorted result while (true) { // Find the minimum element among the // active blocks int minVal = Integer.MAX_VALUE; // Set the minimum // value as the maximum // possible integer int minIdx = -1; for (int i = 0; i < numBlocks; i++) { if (pointers.get(i) < blocks.get(i) .size() // Check if the // pointer is within // the bounds of the // block && blocks.get(i).get(pointers.get(i)) < minVal) { // Check if the value // at the pointer is // less than the // current minimum // value minVal = blocks.get(i).get( pointers.get(i)); minIdx = i; // Update the index of the // block containing the // minimum value } } // If all blocks are exhausted, we're done if (minIdx == -1) { break; } // Otherwise, add the minimum element // to the result and increment the // pointer for that block result.add(minVal); pointers.set(minIdx, pointers.get(minIdx) + 1); } return result; // Return the sorted result } // Driver's code public static void main(String[] args) { // Original Array List<Integer> arr = List.of(7, 7, 4, 1, 5, 3, 2, 0); System.out.print("Input : "); for (int x : arr) { System.out.print(x + " "); } System.out.println(); // Printing result List<Integer> result = grailSort(arr); System.out.print("Output: "); for (int x : result) System.out.print(x + " "); }} |
Python3
# Python code for implementation of the# above approachdef grail_sort(arr): # Split the array into blocks # of size sqrt(n) block_size = int(len(arr) ** 0.5) num_blocks = (len(arr) + block_size - 1) // block_size blocks = [arr[i * block_size:(i + 1) * block_size] for i in range(num_blocks)] # Sort each block using a # comparison sort for block in blocks: block.sort() # Merge the blocks using an algorithm # similar to merge sort # Initialize the pointers to the # beginning of each block pointers = [0] * num_blocks result = [] while True: # Find the minimum element among # the active blocks min_val = float('inf') min_idx = None for i in range(num_blocks): if pointers[i] < len(blocks[i]) and blocks[i][pointers[i]] < min_val: min_val = blocks[i][pointers[i]] min_idx = i # If all blocks are exhausted, # we're done if min_idx is None: break # Otherwise, add the minimum # element to the result and # increment the pointer # for that block result.append(min_val) pointers[min_idx] += 1 return result# Original Arrayarr = [7, 7, 4, 1, 5, 3, 2, 0]print('Input : ', arr)# Printing resultprint("Output: ", grail_sort(arr)) |
C#
// C# implementation for the above approach.using System;using System.Collections.Generic;using System.Linq;class Program{ // grail sort for returning the sorted array static List<int> GrailSort(List<int> arr) { // Split the array into blocks of size sqrt(n) int blockSize = (int)Math.Sqrt(arr.Count); int numBlocks = (arr.Count + blockSize - 1) / blockSize; List<List<int> > blocks = new List<List<int> >(numBlocks); for (int i = 0; i < numBlocks; i++) { blocks.Add(new List<int>(blockSize)); blocks[i].AddRange( arr.Skip(i * blockSize).Take(blockSize)); // copying values from array to blocks // Sort the blocks using insertion sort for (int j = 1; j < blockSize; j++) { int key = blocks[i][j]; int k = j - 1; while (k >= 0 && blocks[i][k] > key) { blocks[i][k + 1] = blocks[i][k]; k--; } blocks[i][k + 1] = key; } } // Merge the blocks using an algorithm // similar to merge sort and initialize // the pointers to the beginning of each block List<int> pointers = new List<int>(numBlocks); for (int i = 0; i < numBlocks; i++) { pointers.Add(0); } List<int> result = new List<int>(); while (true) { // Find the minimum element among the // active blocks int minVal = int.MaxValue; // minVal currently INT_MAX at start int minIdx = -1; for (int i = 0; i < numBlocks; i++) { if (pointers[i] < blocks[i].Count && blocks[i][pointers[i]] < minVal) { minVal = blocks[i][pointers[i]]; minIdx = i; } } // If all blocks are exhausted, we're done if (minIdx == -1) { break; } // Otherwise, add the minimum element // to the result and increment the // pointer for that block result.Add(minVal); pointers[minIdx]++; } return result; } static void Main(string[] args) { // Original Array List<int> arr = new List<int>{ 7, 7, 4, 1, 5, 3, 2, 0 }; Console.Write("Input : "); foreach(int x in arr) { Console.Write(x + " "); } Console.WriteLine(); // Printing result List<int> result = GrailSort(arr); Console.Write("Output: "); foreach(int x in result) { Console.Write(x + " "); } Console.WriteLine(); }}// This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for implementation of the// above approachfunction grail_sort(arr) { // Split the array into blocks // of size sqrt(n) let block_size = parseInt(Math.sqrt(arr.length)); let num_blocks = Math.ceil(arr.length / block_size); let blocks = new Array(num_blocks); for (let i = 0; i < num_blocks; i++) { blocks[i] = arr.slice(i * block_size, (i + 1) * block_size); } // Sort each block using a // comparison sort for (let block of blocks) { block.sort(); } // Merge the blocks using an algorithm // similar to merge sort // Initialize the pointers to the // beginning of each block let pointers = new Array(num_blocks).fill(0); let result = []; while (true) { // Find the minimum element among // the active blocks let min_val = Infinity; let min_idx = null; for (let i = 0; i < num_blocks; i++) { if (pointers[i] < blocks[i].length && blocks[i][pointers[i]] < min_val) { min_val = blocks[i][pointers[i]]; min_idx = i; } } // If all blocks are exhausted, // we're done if (min_idx === null) { break; } // Otherwise, add the minimum // element to the result and // increment the pointer // for that block result.push(min_val); pointers[min_idx]++; } return result;}// Original Arraylet arr = [7, 7, 4, 1, 5, 3, 2, 0];console.log("Input: " + arr.join(" "));let result = grail_sort(arr);// Printing resultconsole.log('Output: '+ result.join(" "));// This code is contributed by Susobhan Akhuli. |
Output
Input : [7, 7, 4, 1, 5, 3, 2, 0] Output: [0, 1, 2, 3, 4, 5, 7, 7]
Time Complexity: O(nlog(n)), where n is the size of the input,
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
