Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
ET3272: Design and Analysis of Algorithm
Name of student: Ekta Ispande Roll No.: 69
Div: B Batch: B3
Date of performance:
Experiment No. 4
Title: Implementation of K-Way Merge Sort Algorithm
Theory/Description of Problem Statement:
1. Merge-Based Approach:
K-Way Merge Sort extends the traditional merge sort by dividing the input into K partitions
instead of two. The merging step involves merging K sorted subarrays simultaneously, ensuring
an efficient sorting process.
Algorithm Steps:
1. Divide the input array into K parts.
2. Recursively sort each part.
3. Merge K sorted subarrays using a merge procedure.
4. Repeat the merging step until a single sorted array is obtained.
Time Complexity: O(n log kn)
Pseudo Code:
KWAY_MERGE_SORT(A, K, n)
if n <= 1:
return A
Divide A into K subarrays
for each subarray:
KWAY_MERGE_SORT(subarray, K, length(subarray))
MERGE_K_SUBARRAYS(A, K, n)
1
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
2. Heap-Based Approach:
This approach uses a min-heap (priority queue) to efficiently merge K sorted arrays. The
smallest element among K lists is always at the top, ensuring efficient merging.
Algorithm Steps:
1. Insert the first element of each sorted subarray into a min-heap.
2. Extract the smallest element and append it to the final array.
3. Insert the next element from the same subarray.
4. Repeat until all elements are merged.
Time Complexity: O(n log K)
Pseudo code:
KWAY_MERGE_HEAP(A, K, n)
Initialize minHeap
for i = 1 to K:
Insert first element of each subarray into minHeap
while minHeap is not empty:
Extract minimum element and append to result
Insert next element from the same subarray (if available)
3. Tournament-Based Approach:
In this approach, a binary tournament tree is used to merge K sorted subarrays efficiently by
repeatedly selecting the minimum element.
Algorithm Steps:
1. Construct a binary tree where leaf nodes represent the heads of K sorted subarrays.
2. Compare nodes pairwise, moving the smallest up the tree.
3. The root node represents the smallest element; extract and replace it with the next
element from the same subarray.
4. Repeat until all elements are merged.
2
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
Time Complexity: O(n log K)
Pseudo code:
BEGIN
FUNCTION winner(pos1, pos2)
RETURN minimum based on tmp values
END FUNCTION
FUNCTION createTree()
Copy array elements into tmp
Build tournament tree
END FUNCTION
FUNCTION recreate()
Update tree after removing smallest element
END FUNCTION
FUNCTION tournamentSort()
CALL createTree()
REPEAT n times:
Store smallest element
Mark as removed
CALL recreate()
END FUNCTION
FUNCTION main()
READ n and array elements
CALL tournamentSort()
PRINT sorted array
END FUNCTION
END
3
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
Analysis of Algorithm
Approach Best Case Average Case Worst Case
Complexity Complexity Complexity
Merge-Based O(n logK n) O(n logK n) O(n logK n)
Heap-Based O(n log K) O(n log K) O(n log K)
Tournament- O(n log K) O(n log K) O(n log K)
Based
Experiment and Result:
1. K ways merge sort
CODE:
import java.util.*;
class mergekways {
public static void mergeKArrays(int[][] arr, int a, int k, int[]
output) {
int c = 0;
for (int i = 0; i < a; i++) {
for (int j = 0; j < k; j++) {
output[c++] = arr[i][j];
}
}
Arrays.sort(output);
}
public static void printArray(int[] arr, int size) {
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
4
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
System.out.print("Enter the number of arrays: ");
int N = sc.nextInt();
System.out.print("Enter the size of each array: ");
int K = sc.nextInt();
int[][] arr = new int[N][K];
System.out.println("Enter the elements of each sorted array:");
for (int i = 0; i < N; i++) {
System.out.println("Enter " + K + " elements for array " + (i +
1) + ":");
for (int j = 0; j < K; j++) {
arr[i][j] = sc.nextInt();
}
}
int[] output = new int[N * K];
mergeKArrays(arr, N, K, output);
System.out.println("Merged sorted array is:");
printArray(output, N * K);
sc.close();
}
}
OUTPUT:
Enter the number of arrays: 2
Enter the size of each array: 5
Enter the elements of each sorted array:
Enter 5 elements for array 1:
1 2 3 4 5
Enter 5 elements for array 2:
6 7 8 9 10
Merged sorted array is:
1 2 3 4 5 6 7 8 9 10
5
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
2. K ways heap sort
CODE:
import java.util.Arrays;
import java.util.Scanner;
public class heapkways {
// Function to heapify a subtree rooted at index i
private static void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Main function to perform heap sort
public static void heapSort(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 elements from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
6
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] arrays = new int[5][5];
// Taking user input for five arrays
for (int i = 0; i < 5; i++) {
System.out.println("Enter 5 elements for array " + (i + 1) +
":");
for (int j = 0; j < 5; j++) {
arrays[i][j] = scanner.nextInt();
}
}
// Merge all arrays into a single array
int[] mergedArray = new int[25];
int index = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
mergedArray[index++] = arrays[i][j];
}
}
// Applying heap sort on the merged array
heapSort(mergedArray);
System.out.println("Sorted merged array: " +
Arrays.toString(mergedArray));
scanner.close();
}
}
OUTPUT:
Enter 5 elements for array 1:
1 2 3 4 5
Enter 5 elements for array 2:
10 12 11 14 13
7
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
Enter 5 elements for array 3:
6 8 9 7 20
Enter 5 elements for array 4:
15 17 16 18 19
Enter 5 elements for array 5:
21 22 23 24 25
Sorted merged array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
3. Tournament sort
CODE:
import java.util.Scanner;
class TournamentSort {
static int n;
static int[] a;
static int[] tmp;
static final int INF = Integer.MAX_VALUE;
static int winner(int pos1, int pos2) {
int u = pos1 >= n ? pos1 : tmp[pos1];
int v = pos2 >= n ? pos2 : tmp[pos2];
return (tmp[u] <= tmp[v]) ? u : v;
}
static void createTree() {
for (int i = 0; i < n; i++) {
tmp[n + i] = a[i];
}
for (int i = 2 * n - 1; i > 1; i -= 2) {
int k = i / 2;
int j = i - 1;
tmp[k] = winner(i, j);
}
}
static void recreate() {
int i = tmp[1];
8
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
while (i > 1) {
int j, k = i / 2;
if (i % 2 == 0 && i < 2 * n - 1)
j = i + 1;
else
j = i - 1;
tmp[k] = winner(i, j);
i = k;
}
}
static void tournamentSort() {
createTree();
for (int i = 0; i < n; i++) {
a[i] = tmp[tmp[1]];
tmp[tmp[1]] = INF;
recreate();
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
n = scanner.nextInt();
a = new int[n];
tmp = new int[2 * n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
scanner.close();
tournamentSort();
// Print sorted array
System.out.println("Sorted array:");
for (int num : a) {
System.out.print(num + " ");
9
Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An Autonomous Institute Affiliated to Savitribai Pune University)
Department of Electronics & Telecommunication Engineering
}
}
}
OUTPUT:
Conclusion:
In this experiment, i analyzed three different approaches to K-Way Merge Sort: Merge-
Based, Heap-Based, and Tournament-Based. The heap-based approach provides optimal
performance with O(n log K) complexity, making it efficient for merging large datasets. The
tournament-based approach offers structured merging, whereas the merge-based approach
remains a simple extension of traditional merge sort. Choosing the best approach depends on
the problem constraints and available computational resources.
10
