Merge algorithm in C: how does this work? [closed]

Question

This C snippet is part of a merge algorithm implementation:

out[i++] = (in1[i1] < in2[i2]) ? in1[i1++] : in2[i2++];

Can someone please explain how it works?

Answer 1

The code

The code uses what is called the post-increment operator and the ternary/conditional operator (see appendix for more details).

A more verbose version may look something like this:

if (in1[i1] < in2[i2]) {
    out[i] = in1[i1];
    i++;
    i1++;
} else {
    out[i] = in2[i2];
    i++;
    i2++;
}

---

The algorithm

If the elements in in1 and in2 are in sorted order, then the snippet serves as the main part of a merge algorithm to merge the two sorted input buffers into one sorted output buffer.

Care must be taken to ensure that i1 and i2 are in-bound for in1 and in2 respectively before comparing in1[i1] against in2[i2]. Then in1[i1] is the next available smallest element in in1, and similarly in2[i2] is the next available smallest element in in2.

Without loss of generality, let's assume in1[i1] < in2[i2] (the other case is a near mirror scenario). Then the next smallest element from in1 is smaller than the next smallest element from in2, and with in1[i1++] on the right hand side of the assignment, we fetch the next smallest value from in1 and advance its pointer to the next available value (if any). With out[i++] on the left hand side of the assignment, we assign the fetched value to a slot in the output buffer and advance its pointer to the next available slot (if any).

A higher-level pseudocode of the overall merge algorithm, using a Queue-like abstract data structure instead of arrays with corresponding pointer indices (for clarity!), may look something like this:

procedure MERGE(Queue in1, in2) : Queue
// given sorted queues in1, in2, return a merged sorted queue

   INIT out IS Empty-Queue

   WHILE in1.notEmpty() AND in2.notEmpty()
      IF in1.peek() < in2.peek()
         out.enqueue(in1.dequeue())
      ELSE
         out.enqueue(in2.dequeue())

   // at this point, at least one of the queue is empty

   // dump in1 to out in case it's not empty
   WHILE in1.notEmpty()
      out.enqueue(in1.dequeue())

   // dump in2 to out in case it's not empty
   WHILE in2.notEmpty()
      out.enqueue(in2.dequeue())

   RETURN out

See also

• Wikipedia/Merge algorithm
• Wikipedia/Mergesort
• Wikipedia/Queue

---

Appendex A: Ternary/conditional operator

Essentially, an expression such as this:

condition ? trueExpr : falseExpr

first evaluates condition, and if it's true, it evaluates trueExpr whose value becomes the value of the entire expression. If instead condition is false, the operator instead evaluates falseExpr, whose value becomes the value of the entire expression.

Related questions

• How does the ternary operator work?
• To ternary or not to ternary?
• Which coding style you use for ternary operator?

---

Appendix B: post-increment operator

An expression such as i++ uses what is called a post-increment operator. The operator increments i, but the value of this expression is the value of i before the increment. By contrast, the value of a pre-increment expression (e.g. ++i) is the value of i after the increment.

There are also pre-decrement (e.g. --i) and post-decrement as well (e.g. i--).

Related questions

• Difference between i++ and ++i in a loop?
• Incrementing in C++ - When to use x++ or ++x?

On pitfalls like i = i++; (most of these is Java, but applicable to other languages as well):

• post increment operator java
• Question about post-increment operator