Understanding Mergesort: Sorting Made Simple | Recursion Series
Вставка
- Опубліковано 15 лип 2024
- Mergesort is a well-known and efficient sorting algorithm that follows the divide-and-conquer paradigm. It aims to sort a given array or list of elements by dividing it into smaller subarrays, sorting those subarrays recursively, and then merging them back together to obtain the final sorted result.
The algorithm begins by repeatedly dividing the input array into two halves until each subarray contains only one element or is empty. This process is known as the "divide" step. Then, it merges adjacent pairs of these subarrays, comparing and rearranging the elements in a sorted order. This merging process continues until a single sorted array is obtained, hence the term "merge" in mergesort.
One of the key advantages of mergesort is its stability, meaning that elements with equal values retain their original relative order after sorting. This property makes mergesort particularly useful in scenarios where preserving the original order of equal elements is crucial.
Mergesort exhibits a time complexity of O(n log n), where "n" represents the number of elements in the input array. This efficiency makes mergesort suitable for sorting large datasets, and it is often used as a standard benchmark for other sorting algorithms.
Overall, mergesort's simplicity, stability, and efficient performance have made it a popular choice in various applications, ranging from general-purpose sorting to applications in data analysis, parallel computing, and more.
0:00 Mergesort overview
2:15 Algorithm animation
3:35 The divide phase
5:10 The conquer phase
5:53 Mergesort pseudocode
7:46 Merge function
Source code repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/algor...
Cool, with animated explanation it`s so much easier to understand!
Hi, appreciate your work!
Here's the list of topics I'd love you to make videos on:
1. Complexity theory: P, NP, etc problems, categorization and how they relate to coding interviews
2. Cover problem solving techniques: sliding window, two pointers, backtracking, etc
3. Cover all sorting methods and their applications
4. Bit manipulations, performance gains, how to optimize a solution to use bits
❤
Really nicely done, very clear. Thank you for sharing.
It is interesting and understandable ❤❤❤
Love your videos! Please consider making some on segment trees. I feel like there aren't great ones out there right now
great explanation and pseudocode example! Thankyou!
First time watching video of yours. Great video
4:24 please consider updating formula for mid point calculation mid = (lo + hi) /2 that might overflow with mid = lo + (hi - lo) / 2
The best!
❤
Please make more videos!
Do you have videos about amotized analysis?
I was wondering which software you use for creating such vibrant illustrations? Is it free to use or open-sourced?
I use Keynote
@@WilliamFiset-videos Thank you for sharing
I comment here because it's your last video and i don't know how to reach to you. If you or actually anyone can help me with this i'll be very greatful. Given a input of a lot of words and an NxM dimension i have to create an algorithm that designs the best (if possible, or one of the bests) sigle-finger NxM keyboard layout for mobile. Which means that, for example, given a letter in the keyboard it's better to have closer letters that you know that with highly probability will come next. An other statement could be that the middle part of the keyboard is best to reach from the finger so it should be the most freqüent letter, so the most important letters should councentrate in the middle meanwhile you consider what i said before about you have closer letters that you know that with highly probability will come next and also you consider the NxM keyboard layout. The frequency of each letter and what letters come next after a certain letter it's easy to get by reading the input words and storing it in a data structure, but once i have this i don't know how to do this algorithm. Obviously you have to find the best combination of letters in the keyboard layout so this if you do it by bruteforce it's exponential and it's impossible to do it in an efficient way. But even if i could, i don't even know how to judge each combination and know which one is the best. I though about making it a graph and get something or even the google's pagerank algorithm which has a similarity, but i got stuck. I also thought about genetic algorithms which would be so efficient to find the best or one of the best, which that's enough. I don't know if i explained myself clearly, if not i'll try to explain it in different words or something. Thanks.
import random
import numpy as np
import networkx as nx
import tensorflow as tf
# Define the keyboard layout structure
N, M = 4, 10 # Number of rows and columns
keyboard_layout = np.empty((N, M), dtype=object)
# Train a machine learning model
model = train_ml_model(letter_frequencies, co_occurrence_probabilities)
# Create a graph
G = nx.Graph()
for letter in letters:
G.add_node(letter)
for letter1, letter2 in zip(letters, letters[1:]):
transition_probability = model.predict([letter_frequencies[letter1], co_occurrence_probabilities[letter1, letter2]])
G.add_edge(letter1, letter2, weight=transition_probability)
# Apply graph-based optimization techniques
layout = nx.spectral_layout(G)
# Optimize with gradient descent
loss_function = define_loss_function(layout, letter_frequencies, co_occurrence_probabilities)
optimizer = tf.keras.optimizers.Adam(learning_rate=0.01)
for epoch in range(100):
with tf.GradientTape() as tape:
loss = loss_function(layout)
gradients = tape.gradient(loss, layout)
optimizer.apply_gradients(zip(gradients, layout))
# Output the optimal layout
optimal_layout = layout
print(optimal_layout)
Hope this might help
Could you do splay tree?
def merge(left, right):
sorted_list = []
l, r = 0, 0
while l != len(left) or r != len(right):
if l == len(left):
sorted_list.append(right[r])
r += 1
elif r == len(right):
sorted_list.append(left[l])
l += 1
elif left[l] < right[r]:
sorted_list.append(left[l])
l += 1
else:
sorted_list.append(right[r])
r += 1
return sorted_list
print(merge([1, 3, 5, 7], [2, 4, 6, 8]))
luv u bro