title: Merge K sorted arrays of Length N
body: <p>This is the problem as stated in the book:</p>
  
  <blockquote>
    <p>Suppose you are given <em>K</em> sorted arrays each with n elements, and you want to combine them into a single array of <em>kn</em> elements. You use the following approach: first merge the first and second arrays, then merge the resulting array with the third array, then the resulting with the fourth, and so on until you merge in the kth and final input array. What is the running time taken by this successive merging algorithm, as a function of <em>k</em> and <em>n</em>, ignoring constant factors and lower-order terms.</p>
  </blockquote>
  
  <p>I know that the when merging the first and second arrays, I'll have at most N comparisons, then the resulting with the third array, I'll have at most 2N comparisons, then merging with the fourth array I'll have at most 3N comparisons and so on.</p>
  
  <p>This results in a total of comparisons of </p>
  
  <p>N + 2N + 3N + 4N + ... + (k - 1)N </p>
  
  <p>however, I'm not quite sure where to go from here. I've tried looking online however they just give the arithmetic summation formula, but I don't quite understand its math and I'm not quite sure how to include k since the summation is only given in terms of n. Can anyone push me in the right direction or help me understand this better?</p>
  
  <p>Thank you!</p>