Merge Sort - Swift Tutorial - iOS Interview Coding Challenge

what's up guys we're back with another Swift interview coding challenge and today I'm gonna be showing you a sorting algorithm called merge sort in Swift and I've actually been asked to implement merge sort during one of my phone screen interviews so hey you never know alright let's dive in before we dive into the code I want to give a huge hat tip to Thomas handing in his blog he has a ton of great Swift tutorials I highly recommend checking it out this blog actually really helped me understand how merge sort worked and how to code it up and Swift so I got to give credit where credit is due he has a great blog definitely go check it out okay so what a high-level merge sort is really done in two steps the first step is you keep chopping your right in half until each element is in its own single array and then once you have each element in its own single array then you start combining those array while sorting them through the process let me walk you through that so here we have our array at the top of eight numbers they're just randomized jumbled and the first step again is to keep chopping it in half until you get each number in its own array as you can see here we have eight individual arrays each containing its own number and now that we have each element in its own array now we can start combining them and we combine them two at a time I put these red lines here to kind of separate them for you so you see we have 7 & 3 1 & 8 5 & 4 2 & 6 all right let's start combining them so the way we combine these arrays is we compare the first element in the left array in the first element in the right array whichever one is less we append it to a new array now in this particular circumstance we only have one item in each array so they both happen to be the first item but you'll see how that plays out as the array grows so first let's compare 7 & 3 let's create our new array here 3 is less than 7 so we append that one first so it's 3 comma 7 then now looking at 1 & 8 this one is already in order so we have 1 comma 8 and then here 5 & 4 4 smaller so 4 gets appended first so 4 comma 5 and then here we have 2 & 6 this again is already in order so if 2 comma 6 and then this just continues to play out so again we're comparing the first elements in the left in the right array so we're gonna compare 3 to 1 in this case 1 is less than 3 so 1 goes in there first then we go ahead and remove it from the array now 3 now we compare 3 & 8 because 8 is now the first element because 1 is gone 3 is less so we go ahead and append and we get rid of the three here now we compare seven and eight seven is less and then we get rid of the seven and then now it gets appended here as well so now that array is in order and then the same thing over here compare four two two two goes first two is gone from the array compare four and six and you get four fours gone from the array now five and six now five goes down here five has gone from the array and then you just bring six down and then finally we just rinse and repeat to get the final array so we're comparing one and two again because we're the first elements one goes in there because it's less get rid of one now we're comparing three and two two comes down get rid of the two and you guys see where I'm going but I'm gonna finish it out anyway now we compare seven and six six is less it's fine get rid of the six and then now we would just append this array because this rate is automatically in order because we've been sorting it the whole time so now we can just bring down because there's nothing to compare it to in the right array we can just bring down seven and eight and just append the whole contents of the left right to the end and now you see here we have a sorted array and that is merge sort so as you just saw in that illustration merge sort is really composed of two steps first you split up the array and then you merge them all together let's talk about splitting up the array first now this function we're about to write is our main function and this is what we're actually going to call our merge function so what we're gonna do is I'm gonna write about 90% of this function then we're going to switch to our merge function write all of that and then come back to this function and finish it off okay so here on line four our merge sort function is going to take in an array and this is the array that we're gonna sort and then it returns another array of int which is gonna be our sorted array so again this one's gonna be unsorted it's gonna spit out a sorted one and for right now we're just returning an empty array we'll fix that later okay so the first thing we're gonna check before we start splitting up these arrays is to make sure the array has more than one object right you can't split an array that only has one object so let's do that okay so again we're just checking that with a guard statement so what this is doing is basically if array account is greater than one we'll go ahead and continue on with the rest of our code that doesn't exist yet if a rate count is less than one we'll go into our else statement and we're just going to return the array again this is only going to go into the else statement if the array is has one object or less so if that is the case we can't split it up anymore we're just going to return that array that has the single object in it okay so now that we know that our array has more than one object let's split it up alright so here on lines 10 and 11 we're just splitting up our array we're letting the left side of the array is going to equal 4 creating a new array and it's from our existing array and then the indices we're taking what I've highlighted here is we're gonna take from index 0 all the way up to but not including that's what this dot dot less than means so real quick if you do got less than that means you're taking up to but not including the last value however if you just did dot dot dot like three dots that means you're including the last value we don't want to include the array dot count divided by two which is the middle index because that's going to be included in the right-hand side of the array so so we're gonna take 0 up to but not including a red count divided by two which is the middle index and that's going to be our left side of the array and then very similar on the right side of the eye right here same thing we're creating an array except this time the indices were taking our array dot count divided by two and we're including that remember because we went up to but not including array count / - so now we're including that in the right-hand side of the array and then we're going up to but not including array dot count and the reason we do not including is because array dot count is always going to be one extra number because arrays start at zero not at one so for example if you have 10 objects in the array already that comma is going to be ten however the highest ended index is going to be nine because already start at index zero okay so that's it we've split up our array again we're gonna come back to this function when it comes time to return the sorted array because here on line 13 this is where we're actually going to run our merge function and call it recursively you'll see what I mean when we come back to it in a little bit but for right now we're gonna leave a blank and move on to our merge function alright so our merge function has to take into arrays let me write out the function signature now so again we're taking in two arrays here we're just calling it left and right so we have our left array of intz and then our right array of ins and then we're going to return our combined array events so the first thing we need to do is we need to create three variables we need our merge list which is going to be our DeRay from the two arrays and then we're gonna need a left and a right which basically makes the arrays that we passed into the parameters mutable because by default what we pass in here and left and right these are immutable arrays so let's go and write that up okay so like I said line 19 here we have our merged array this is what we're going to build as we go through the code and then right here in lines 20 and 21 we're basically just taking our parameters that we passed in these two arrays and by creating VARs that are equal to those arrays now this left in this right are gonna be mutable arrays because we're gonna be altering these arrays as we go and then now for the final part we just need a while loop let me type that up and then we'll walk through it so let me explain lines 23 to 30 so the condition for our while loop is while the left count is greater than zero and which means both of these has to be true right count is greater than zero so we're only gonna run this for loop if there's elements in both the left array and the right array and as you saw in the illustration we're gonna compare the first element in the left array against the first element in the right array and then if the first element in the left array is less now we're gonna go ahead and run line 26 where we're gonna append that element from the left array and we're gonna do that using a method called remove first what remove first does is it pulls off the first element of the array and then basically shifts everything down for example if my array had the numbers 1 2 3 in it and then I removed first I remove the 1 now my array only has 2 and 3 so again what line 26 is doing it is basically just taking that first element from the left array and putting it into the merged array in conversely on line 28 here in our else statement this is going to execute if the element in the right array is smaller so again merger a dot append and then we're just going to remove the first item and put it in a merged array from the right array so all we're doing is comparing the first element in the left array to the right array whichever one is less we're gonna append that to the merged array and then we're gonna keep on repeating that until we hit the condition on our while loop which is that both of the arrays have at least one element so now you might be thinking well what if after all this sorting the left array still has you know 4 elements left in it in the right array has 0 elements that's fine because we can just append the entire content of the left array to the end and actually let me go ahead and type this out so it makes more sense so here we're gonna return merged array then we're going to append on the left array and then append the right array whatever is left in it because this also could be empty and back to what I was saying if the left array still had four elements left in it in the right array had zero we know the elements in the left array are ordered because remember the very first thing we did in merge sort was split everything into its own array so each number had its own array so at this point we know that if an array has more than one number it's already been sorted so that's why in that situation where if the left array has four numbers left and the right array has no numbers left we can just go ahead and append the entire contents of the left array or right already if that is the case so just to drive the point home in that example where the left array had four numbers remaining what happens here what we return is we return the merged array so everything we built and then we append on the entire contents of the left array which is those four numbers remaining and then we add the right array which has nothing in it so this is kind of like adding zero to a number in math all right so let me give one more quick recap on this whole function so we're taking in two arrays a left array and a right array now we're creating our merged array which is what we're gonna build as we sort these numbers and then these two variables here are just to create arrays that are mutable based on our left and right array and then here on our while loop this is where we compare the first element of each array and whichever one is smaller we append it to our merged array and that's how we get the ordered merged array and on on line 32 we're returning a merged array plus you know whatever's left from our left and right array that are already in order so this is how we're sorting and merging two arrays remember how I said we're gonna write about 90% of this function right this whole function and then come back so now here's what we need to call the merge function we just wrote okay so here line 13 it's a long one but it can be broken down pretty easy so remember this merge sort is returning an array of intz so we need to return an array events here on line 13 well our merge function here also returns an array of events so that's what we're doing returning the result of this merge function and then as you can see a merge takes in a left array and a right array and this is running merge sort out what's called recursively which means it keeps calling itself so basically he's gonna keep running merge sort on this left array right here so let's say this left array has ten elements in it after we split it up so so this main one had 20 in it so now our left one only has ten because it's the first half so this is gonna run merge sort repeatedly remember I said what merge sort does is it keeps splitting the array until each number in the array is in its own array so that's why you keep running this recur this will keep splitting the array until each number is in its own array so that's what we're running here on line 13 is the result of recursively running merge sort on each side of the array and then finally once we've done that we go ahead and merge the left and right side of the recomposed sorted array alright let's test it out so let me create a large random list here real quick okay so what I've done here on line 35 to 40 is I just created a quick array and then here I did a for loop where I'm just creating a random int where the upper bound is a thousand and then just appending that random int so basically we're going to get an array of 50 random integers 0 to a thousand so let's go ahead and print that real quick just so you guys can get a visual of what we're looking at here so as you can see down on my console just a bunch of random number zero to a thousand not in order at all so let's go ahead and there might be a better way to do this but I just do this when I want a space just do an empty print statement so now let's go ahead and print merge sort so print now we're gonna run merge sort in the array we're gonna pass in is numbers which I just created and this should sort that array of numbers yep so again this first one is the unsorted array and then now you know this space is that empty print statement and then now here are in merge sort and look all these numbers all these 50 numbers are sorted so that is a recursive version of merge sort written in Swift all right so that's merge sort in Swift there are more Swift coding challenges on the way if you found this at all useful go and hit subscribe I put out new videos all the time

Channel: Sean Allen

Views: 18,599

Keywords: Merge Sort Swift, Merge Sort in Swift, Sorting Algorithms, Merge Sort explained, Merge sort tutorial, merge sort swift tutorial, Swift, Swift Tutorial, iOS Interview Question, iOS Interview Questions and answers, Swift Interview Questions, Swift interview questions and answers, iOS Developer, iOS Development, Learn Swift, Merge Sort, Swift merge sort, merge sort algorithm

Id: DfO089qWEE8

Length: 12min 41sec (761 seconds)

Published: Thu Jul 06 2017