Learn Merge Sort in 13 minutes 🔪
Bro Code
https://www.youtube.com/watch?v=3j0SWDX4AtU

Transkript (automatisch erstellt)

0:00 hey what's going on everybody it's you bro hope you're doing well and in this video we're going to discuss the merge sword algorithm in computer
0:07 science so sit back relax and enjoy the show all right what's going on people merge sword merge sword is
0:16 a divide and conquer algorithm basically what we do is that we will pass an array as an argument to a
0:22 merge sort function this function is going to divide our array in two we have a left array and a right array these will be sub-arrays and we will
0:31 copy the elements over from our original array to our two new sub-arrays and merge sword is a recursive function
0:39 so at the end of merge sort we will call merge sword again and pass in our subarrays that we create and again the merge sort function is
0:47 going to divide our arrays in two by creating a two new sub arrays and then copy the elements over and we will stop when our arrays only
0:55 have a size of one and that's where sorting then merging come in and with the process of merging and sorting we will create a
1:03 second helper function named merge merge will accept a total of three arguments our left subarray our right subarray and the original subarray in which
1:13 these elements came from merge is going to take these elements and put them back into their original array which they came from
1:20 in order and we will do the same thing with the next grouping of arrays until all of these elements are merged back into their original array in which
1:28 they came from all in order now in practice when we do execute this merge sort function instead of tackling all of these
1:36 sub-arrays like one layer at a time we will tackle them by one branch at a time so it's going to look a little something
1:43 like this where we will start with the leftmost branch and then work our way towards the right so i'll speed up the footage and just give you a
1:51 rundown of how this works in practice [Music] [Music]
3:03 you [Music] [Music]
3:31 [Music] [Music]
3:50 [Music] me [Music]
4:11 and that ladies and gentlemen is the merge sort algorithm the merge sort algorithm has a runtime complexity
4:18 of big o of n log n it runs in quasi-linear time along with quick sort and heap sort which we still need to talk about
4:26 so when working with large data sets merge sort is faster than insertion sort selection sort and bubble sort
4:33 but on the other hand the emerge sword algorithm uses more space than a bubble sword selection sword and insertion sort because we need to create
4:41 new subarrays to store elements whereas bubble sort selection sword and insertion sort can sort in place so they use a constant amount of space
4:49 to do their sorting unlike with merge sort now let's move on to the hands-on portion of this video and create a merge sort function in code
4:57 now all right well let's get started we'll need an array to work with make up some numbers make sure that
5:03 they're not in order as well as a for loop to iterate over the elements of our array so currently our array is not in order
5:10 but that's going to change soon let's invoke a merge sort method that we still need to declare this is going to be a recursive method
5:17 and we will pass in an array and each time that we invoke this method we will split our array in half create two sub-arrays and
5:25 then copy the elements over so let's create and declare this method private static void merge sort and we'll need a helper method
5:34 too and we'll name this merge a helper method is just a method that helps another method basically so private static void merge
5:45 and there's going to be three parameters within our merge method int left array
5:53 int right array and int array remember that these are arrays of integers the first thing that we're
6:04 going to do within our merge sort method is that we need to get the length of our array so let's cache that within a local
6:11 variable named length int length equals array.length and we'll need a base case too when do we stop recursion
6:22 if length is less than or equal to one then we shall return and this is our base case basically with
6:32 this merge sort method we're dividing our ray in two each time if the length is one there's no longer a need to divide our array further
6:40 and we'll need to find the middle position of our ray int middle equals length divided by two and we'll create two new sub arrays
6:53 int array left array equals new integer array and the size is middle and we'll create a right array
7:05 integer array right array the size is length minus middle okay now we need to copy the elements of our original array to our left and right
7:16 arrays so we'll need two indices int i equals zero this will be for our left array
7:26 and int j equals zero and this is for our right array then let's create a for loop we don't necessarily need to declare a new
7:42 index here we can just use i so i'm going to add a semicolon our condition is i is less than length then increment
7:53 i by 1 during each iteration so our condition is with an if statement if i is less than
8:00 middle then we will copy an element from our original array to our left array left array at index of i
8:12 equals array at index of i else we will copy that element to our right array
8:24 else right array at index of j remember that this index is for the right array equals array at index of i
8:35 then let's increment j by one okay this is where recursion comes in so outside of this for loop we will call merge sword again
8:45 and pass in our left array so we'll consistently divide our array in half we'll begin by dividing the left array
8:54 then the right array with a separate recursive call so left array then right array and then call merge
9:03 so with merge we have to pass in our left array right array and our original array because we'll put the elements back in order
9:10 left array right array and our original array that we received as an argument so that is it for the
9:17 merge sort function let's work on merge next first thing that we're going to do within the merge method is cache the size of our left array and right
9:25 array within some local variables int left size equals array dot length divided by 2 and right size equals
9:38 array dot length minus left size and then we'll need three indices int i equals zero this is for our original array to keep
9:51 track of the position l will be in charge of our left array and r will be in charge of our right array
9:59 and these will be the indices that we're using okay the next part we're going to check
10:06 the conditions for merging and we can do this with a while loop so our condition is going to be while l
10:16 is less than left size and r is less than right size so basically while there's elements within
10:27 both our left array and right array we will continue adding elements to our original array and we'll need to check to see which
10:35 element is smaller if left array at index of l is less than right array
10:47 at index of r then we will copy the element from our left array to our original array so we're basically comparing the
10:55 number on the left to the right and adding whatever number is smaller back to our original array so array at index of i
11:05 equals left array at index of l then we can increment i increment l
11:17 so if the number on the left is not smaller than the number on the right we have to copy the element in our right array
11:23 to our original array and we can use an else statement else array at index of i equals right array at index
11:35 of our increment i increment r so there's probably going to be one element remaining that we cannot compare to another element because there's only
11:45 one left so let's write a while loop for that condition while l is less than left size
11:56 then we will take array at index of i equals left array at index of l increment i increment l
12:11 then we'll need a another while loop if r is less than right size we will copy the last right element over
12:22 array at index of i equals right array at index of r increment i increment r and that should be it let's run this
12:38 and our array is now sorted in conclusion everybody the merge sort algorithm recursively divides an array in two
12:46 sorts them and then recombines them the merge sort algorithm has a runtime complexity of big o of n log n and a space complexity
12:56 of big o of n so that is the merge sort algorithm if you would like a copy of this code i will post this to the comment section
13:04 down below and well yeah that is the merge sword algorithm in computer science hey you
13:11 yeah i'm talking to you if you learned something new then help me help you in three easy steps by smashing that like button
13:18 drop a comment down below and subscribe if you'd like to become a fellow bro [Music]
13:44 you