Merge Algorithms - 2-Way and K-Way Merge
Say in a programming interview situation, you are given two sorted arrays of integers and asked to merge them. What would you do? I'm pretty sure my first instinct would be to append them. Which then I would realize that the new array would be no longer be properly sorted. The correct approach to this problem is to use a 2-way merge.
2-way merge is quite simple. You take two sorted arrays. You compare the first element in each array and then take the smaller one and put it into a separate union array. And you keep doing this until you have fully merged the two arrays. This will end up having a nice O(n) time complexity, as you only do one comparison for each element.
Now imagine that instead of two arrays, you are given six arrays. Enter k-way merge. Merging k sorted arrays using an optimal approach like using a heap is called k-way merge. However, you can use tournament trees for optimum time, which will result in Θ(n logk) time complexity. If you want to see full visualization of 2-way and k-way merge in action, check out the video. The entire video is animated, as I believe that animations are the best way to comprehend sorting and merging algorithms.
Outline of this video:
0:00 Overview
0:22 2-Way Merge
0:50 K-Way Merge
2:44 Merge Algorithms Time and Space Complexities
4:04 Relationship of K-Way Merge and Distributed Computing
5:33 What Are the Caveats of K-Way Merge w/ Tournament Trees?
5:51 Tips!
Merge algorithm source code:
https://github.com/soygul/QuanticDev/...
Further reading:
https://en.wikipedia.org/wiki/Merge_a...
https://en.wikipedia.org/wiki/K-way_m...
https://www.geeksforgeeks.org/tournam...
If you want to read or contribute, you can find this guide on:
https://quanticdev.com/algorithms/merge
My Algorithms Playlist:
• Algorithms
- - - - - - - - - -
/ quanticdev
/ quantic_dev
https://quanticdev.com
- - - - - - - - - -
Next Video:
K-way merge using tournament trees is one of the fundamentals of streaming data processing and distributed computing. For instance, distributed sorting (external sorting). In my next algorithm video, I will solve an interview question asked by Google during a Senior Reliability Engineering interview. In that question, you are given a 1 TB of data and 1000 computer nodes with only 1 GB of RAM each. And you are asked to sort this data as fast as possible while utilizing the given computer nodes as efficiently as possible. There are several ways to solve this problem, and k-way merge using tournament trees is one of the optimal solutions. In that video, I will go over all possible solutions. If you don't want to miss it when it is out, don't forget to sub.
